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

Abstract

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.