.879-approximation algorithms for MAX CUT and MAX 2SAT

Abstract

We present randomized approximation algorithms for the MAX CUT and MAX 2SAT problems that always deliver solutions of expected value at least .87856 times 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. We then show how to derandomize the algorithm to obtain approximation algorithms with the same performance guarantee of .87856. The previous best-known approximation algorithms for these problems had performance guarantees of ~for MAX CUT and ~for MAX 2SAT. A slight extension of our analysis leads to a .79607-approximation algorithm for the maximum directed cut problem, where a & approximation algorithm was the previous best-known algorithm. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and, to the best of our knowledge, represents the first use of semidefinite programming in the design of approximation algorithms.