IMPROVED APPROXIMATION ALGORITHMS FOR MAXIMUM CUT AND SATISFIABILITY PROBLEMS USING SEMIDEFINITE PROGRAMMING

We present randomized approximation algorithms for the maximum cut (MA X CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always de liver solutions of expected value at least .87856 times the optimal va lue. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relax ation can be interpreted both as a semidefinite program and as an eige nvalue minimization problem. The best previously known approximation a lgorithms for these problems had performance guarantees of 1/2 for MAX CUT and 3/4 for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem ( MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the b est previously known approximation algorithms had performance guarante es of 1/4 and 3/4, respectively. Our algorithm gives the first substan tial progress in approximating MAX CUT in nearly twenty years, and rep resents the first use of semidefinite programming in the design of app roximation algorithms.