Journal of the ACM Bibliography

Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, November 1995. [BibTeX entry]
Preliminary version

A preliminary version of these results was presented in: Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms; G.3 [Probability and Statistics] -- probabilistic algorithms (including Monte Carlo); I.1.2 [Algebraic Manipulation]: Algorithms -- analysis of algorithms

General Terms: Algorithms

Additional Key Words and Phrases: Approximation algorithms, convex optimization, randomized algorithms, satisfiability

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database