About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM (JACM)
Paper
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.