Improved Approximation Algorithms for Maximum Cut and Satisflability Problems Using Semidefinite Programming
- Michel X. Goemans
- David P. Williamson
- 1995
- Journal of the ACM (JACM)
Publications
Date
Featured collections
Popular topics
29 results for David P. Williamson
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Lisa Fleischer
- Kamal Jain
- et al.
- 2006
- Journal of Computer and System Sciences
Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation
- Fabián A. Chudak
- Tim Roughgarden
- et al.
- 2004
- Mathematical Programming
Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming
- Michel X. Goemans
- David P. Williamson
- 2004
- Journal of Computer and System Sciences
A primal-dual schema based approximation algorithm for the element connectivity problem
- Kamal Jain
- Ion Mǎndoiu
- et al.
- 2002
- Journal of Algorithms
The primal-dual method for approximation algorithms
- David P. Williamson
- 2002
- Mathematical Programming, Series B
Improved approximation algorithms for MAX SAT
- Takao Asano
- David P. Williamson
- 2002
- Journal of Algorithms
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
- R. Ravi
- D.P. Williamson
- 2002
- Algorithmica (New York)
An iterative rounding 2-approximation algorithm for the element connectivity problem
- Lisa Fleischer
- Kamal Jain
- et al.
- 2001
- Annual Symposium on Foundations of Computer Science - Proceedings
Gadgets, approximation, and linear programming
- Luca Trevisan
- Gregory B. Sorkin
- et al.
- 2000
- SIAM Journal on Computing