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