1994 · 239 citations · 26 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisApproximation AlgorithmsApproximation MethodsCombinatorial OptimizationInteger ProgrammingOptimization TheoryMaximum Cut Approximation
We present randomized approximation algorithms for the MAX CUT and 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. We then show how to derandomize the algorithm to obtain approximation algorithms with the same performance guarantee of .87856. The previous best-known approximation algorithms for these problems had performance guarantees of ~for MAX CUT and ~for MAX 2SAT. A slight extension of our analysis leads to a .79607-approximation algorithm for the maximum directed cut problem, where a & approximation algorithm was the previous best-known algorithm. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and, to the best of our knowledge, represents the first use of semidefinite programming in the design of approximation algorithms.
26
Some simplified NP-complete graph problems
M. R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science · 1976 · 2.1K citations
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text
On the Shannon capacity of a graph
László Lovász · IEEE Transactions on Information Theory · 1979 · 1.7K citations