Home Bookmarks Papers Blog

MAX CUT/MAX 2SAT Approximation using Semi-definite programming

Using semi-definite programming, Goemans and Williamson showed that one can do 0.8785-approximation to MAX-2SAT and the MAX CUT problems. Their paper is avliable here.

For the general MAX SAT problem, the currently best algorithm, is due to Asano and Williamson, available here. They show 0.7846-approximation.

Hastad showed that one can NOT do better than 0.875-approximation to MAX SAT unless P=NP. Note that there is still a gap between the lower and upper bound.

Trying to close this gap, Eran Halperin and Uri Zwick showed a 0.8742-approximation for MAX 4-SAT (so very close to the value of 0.875).

Earlier, Karloff and Zwick showed an optimal 7/8-approximation algorithm for MAX 3SAT (note that in this paper this result is conjectured, but since then it was proved).

MAX kSAT is the variant of MAX SAT where each cluase is made out of at most k variables. Note that if each clause has >= 3 variables, then 7/8-approximation is easy using randomized assignement. Thus, it is somewhat surprising that one has to resort to SDP (semi-definite programming) to achieve good approximation in the general case.

The problem of max-sat is related to constraint satisfaction and learning, but have a lot of other applications. People currently can solve such instances when their size is relatively small.


Back to course home page


Last updated: Thu Apr 26 10:25:00 CDT 2001