Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems

Understand

Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems.

• In particular, the random hyperplane rounding method of Goemans and Williamson has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications.
• Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, the tight approximation ratio is still unknown.
• One of the main reasons for this is the fact that very few techniques for rounding semidefinite relaxations are known.