How good is the Goemans-Williamson MAX CUT algorithm?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How good is the Goemans-Williamson MAX CUT algorithm?

Full text

Pdf (631 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 427 - 434

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Howard Karloff

College of Computing, Georgia Institute of Technology, Atlanta, GA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 61, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.237990 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BM	Francisco Barahona , Ali Ridha Mahjoub, On the cut polytope, Mathematical Programming: Series A and B, v.36 n.2, p.157-173, Nov. 1986 [doi>10.1007/BF02592023]
	Delsarte	P. Delsarte, "Hahn Polynomials, Discrete Harmonics, and t-Designs," SIAM Journal on Applied Math 34 (1978), 157-166.
	FG	U. Feige and M. X. Goemans, "Approximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DI- CUT,~ Proc. Third Israel Symposium on Theory of Computing and Systems, Israel, 1995.
	GW	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	KMS	D. Karger, R. Motwani, and M. Sudan, "Approximate Graph Coloring by Semidefmite Programming," Proc. S5th A CM Symposium on the Foundations of Computer Science (1994), Santa Fe, 2-13.
	Knuth	D. Knuth, "Combinatorial Matrices," notes of Institut Mittag-Leffier, Nov., 1991, revised Jan., 1993.

CITED BY 6

	Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States
	Uriel Feige , Marek Karpinski , Michael Langberg, Improved approximation of max-cut on graphs of bounded degree, Journal of Algorithms, v.43 n.2, p.201-219, May 2002
	Rakesh Agrawal , Sridhar Rajagopalan , Ramakrishnan Srikant , Yirong Xu, Mining newsgroups using networks arising from social behavior, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States
	Wenceslas Fernandez de la Vega , Claire Kenyon-Mathieu, Linear programming relaxations of maxcut, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.53-61, January 07-09, 2007, New Orleans, Louisiana
	Noga Alon , Benny Sudakov, Bipartite Subgraphs and the Smallest Eigenvalue, Combinatorics, Probability and Computing, v.9 n.1, p.1-12, January 2000