Journal of the ACM (JACM)

Improved Approximation Algorithms for Maximum Cut and Satisflability Problems Using Semidefinite Programming

Download paper


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 .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. The best previously known approximation algorithms 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 best previously known approximation algorithms had performance guarantees of 1/4 and 3/4, 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. Categories and Subject Descriptors: F2.2 [Analysis of Algorithms and Problem Complexity]: Nonumerical Algorithms and Problems-computations on discrete structures; G2.2 [Discrete Mathematics]: Graph Theory-graph algorithms; G3 [Probability and Statistics] probabilistic algorithms (including Monte-Carlo); 11.2 [Algebraic manipulation]: Algorithms-analysis of algorithm. General Terms: Algorithms. © 1995, ACM. All rights reserved.



Journal of the ACM (JACM)