Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856times the optimal value.These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation.This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem.The best previously known approximation algorithms for these problems had perfc~rmance guarantees of ~for MAX CUT and ~for MAX 2SAT.Slight extensions of our analysis lead to a .79607-approximationalgorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximationalgorithm for MAX SAT, where the best previously known approxim ation algorithms had performance guarantees of ~and ~, respectively.Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of :semidefinite programming in the design of approximation algorithms.