Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X. Goemans, David P. Williamson · Journal of the ACM · 1995
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.
Cited by 3,583 works. doi:10.1145/227683.227684 Open-access PDF
Authors
References
- The Art of Computer Programming
- Matrix Computations
- The Theory of Matrices
- Linear Matrix Inequalities in System and Control Theory
- The Art of Computer Programming
- Graph Theory with Applications
- The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
- Reducibility Among Combinatorial Problems
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems