.879-approximation algorithms for MAX CUT and MAX 2SAT

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

.879-approximation algorithms for MAX CUT and MAX 2SAT

Full text

Pdf (1.09 MB)

Source

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

Montreal, Quebec, Canada

Pages: 422 - 431

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Michel X. Goemans	Dept. of Mathematics, Room 2-372, M. I. T., Cambridge, MA
David P. Williamson	School of Operations Research and Industrial Engineering, 237 ETC Building, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 75, Citation Count: 41

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/195058.195216 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.

	1	F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. To appear in SIAM Journal on Optimization. A preliminary version appeared in the Proc. 2nd IPCO, 1992.
	2	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd FOCS, pages 14-23, 1992.
	3	Francisco Barahona , Martin Grötschel , Michael Jünger , Gerhard Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, v.36 n.3, p.493-513, May/June 1988 [doi>10.1287/opre.36.3.493]
	4	Charles Delorme , Svatopluk Poljak, Combinatorial properties and complexity of a max-cut approximation, European Journal of Combinatorics, v.14 n.4, p.313-333, July 1993 [doi>10.1006/eujc.1993.1035]
	5	C. Delorme , S. Poljak, Laplacian eigenvalues and the maximum cut problem, Mathematical Programming: Series A and B, v.62 n.3, p.557-574, Dec. 8, 1993 [doi>10.1007/BF01585184]
	6	C. Delorme , S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Mathematics, v.111 n.1-3, p.145-156, Feb. 22, 1993 [doi>10.1016/0012-365X(93)90151-I]
	7	U. Feige and M. X. Goemans. Personal communication, 1994.
	8	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	9	M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237-267, 1976.
	10	Michel X. Goemans , David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, v.7 n.4, p.656-666, Nov. 1994 [doi>10.1137/S0895480192243516]
	11	G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, MD, 1983.
	12	M. Gr5tschel, L. Lovhsz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
	13	M. Gr6tschel, L. Lov#sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988.
	14	F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4:221-225, 1975.
	15	D. J. Haglin. Approximating maximum 2-CNF satisfiability. Parallel Processing Letters, 2:181-187, 1992.
	16	D. J. Haglin. Personal communication, 1994.
	17	David J. Haglin , Shankar M. Venkatesan, Approximation and Intractability Results for the Maximum Cut Problem and Its Variants, IEEE Transactions on Computers, v.40 n.1, p.110-113, January 1991 [doi>10.1109/12.67327]
	18	D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In preparation, 1994.
	19	R. M. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York, NY, 1972.
	20	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	21	P. Lancaster and M. Tismenetsky. The Theory of Matrices. Academic Press, Orlando, FL, 1985.
	22	L. LovLsz. On the Shannon capacity of a graph. IEEE Transactions on Information Theory, IT-25:1- 7, 1979.
	23	L. Lovhsz. Combinatorial optimization: Some problems and trends. DIMACS Technical Report 92-53, 1992.
	24	L. Lovhsz and A. Schrijver. Matrix cones, projection representations, and stable set polyhedra. In Polyhedral Combinatorics, volume 1 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 1-17. American Mathematical Society, 1989.
	25	L. Lov#z and A. Schrijver. Cones of matrices and sctfunction#, and 0-1 optimization. SIAM Journal on Optimization, 1:166-190, 1990.
	26	B. Mohar and S. Poljak. Eigenvalues in combinatorial optimization. Technical report, University of Ljubljana, 1992.
	27	Y. Nesterov and A. Nemirovskii. Self-Concordant Functions and Polynomial T#me Methods in Convex Programming. Central Economic and Mathematical Institute, USSR Academy of Science, .Moscow, 1989.
	28	Y. Nesterov and A. Nemirovskii. Interior Point Polynomial Methods in Convex Programming. Society for Industrial and Applied Mathematics, 1{993.
	29	G. I. Orlova and Y. G. Dorfman. Finding the maximal cut in a graph. Engineering Cybernetics, pages 502- 506, 1972.
	30	Michael L. Overton , Robert S. Womersley, On the sum of the largest eigenvalues of a symmetric matrix, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.41-45, Jan. 1992 [doi>10.1137/0613006]
	31	M. L. Overton , R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Mathematical Programming: Series A and B, v.62 n.2, p.321-357, Nov. 15, 1993 [doi>10.1007/BF01585173]
	32	C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991.
	33	G. Pataki. Algorithms for cone-optimization problems and semi-definite programming. Manuscript, 1993.
	34	S. Poljak and F. Rendl. Solving the max-cut problem using eigenvalues. Report 91735-OR, Institute fiir Diskrete Mathematik, Universit#it Bonn, 1991.
	35	S. Poljak and F. Rendl. Nonpolyhedral relaxations of graph-bisection problems. DIMACS Technical Report 92-55, 1992.
	36	S. Poljak and F. Rendl. Computational experiments with node and edge relaxations of the max-cut problem. Report 266, Technische Universit~t Graz, 1993.
	37	S. Poljak and D. Turz#. A polynomial algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem. Canadian Journal of Mathematics, 34:519-524, 1982.
	38	S. Poljak and Z. Tuza. The max-cut problem- a survey. Manuscript, 1993.
	39	F. Rendl, R. Vanderbei, and H. Wolkowicz. Interior point methods for max-min eigenvalue problems. Report 264, Technische Universit~t Graz, 1993.
	40	Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
	41	P. M. Vaidya. A new algorithm for minimizing convex functions over convex sets. In Proc. 30th FOCS, pages 338-343, 1989.
	42	P. M. Vithnyi. How well can a graph be n-colored? Discrete Mathematics, 34:69-80, 1981.
	43	H. Wolkowicz. Some applications of optimization in matrix theory. Linear Algebra and Its Applications# 40:101-118, 1981.
	44	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States

CITED BY 41

	Hans L. Bodlaender , Klaus Jansen, On the complexity of the maximum cut problem, Nordic Journal of Computing, v.7 n.1, p.14-31, Spring 2000
	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States
	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Philip Klein , Hsueh-I Lu, Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.338-347, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Laxmi Parida , Bud Mishra, Partitioning K clones: hardness results and practical algorithms for the K-populations problem, Proceedings of the second annual international conference on Computational molecular biology, p.192-201, March 22-25, 1998, New York, New York, United States
	Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	M. V. Marathe , H. B. Hunt, III , R. E. Stearns , V. Radhakrishnan, Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.468-477, May 23-25, 1994, Montreal, Quebec, Canada
	Jonathan Berry , Mark Goldberg, Path optimization and near-greedy analysis for graph partitioning: an empirical study, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 22-24, 1995, San Francisco, California, United States
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms, v.42 n.1, p.173-202, January 2002
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.96-105, January 09-11, 2000, San Francisco, California, United States
	Takao Asano , Takao Ono , Tomio Hirata, Approximation algorithms for the maximum satisfiability problem, Nordic Journal of Computing, v.3 n.4, p.388-404, Winter 1996
	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
	Gerald Gruber , Franz Rendl, The bundle method for hard combinatorial optimization problems, Combinatorial optimization - eureka, you shrink!, Springer-Verlag New York, Inc., New York, NY, 2003
	Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences, v.67 n.2, p.212-243, September 2003
	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States
	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
	Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.596-605, May 29-June 01, 1995, Las Vegas, Nevada, United States
	H. Noltemeier , H.-C. Wirth , S. O. Krumke, Network design and improvement, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Noga Alon , Pierre Kelsen , Sanjeev Mahajan , Hariharan Ramesh, Coloring 2-colorable hypergraphs with a sublinear number of colors, Nordic Journal of Computing, v.3 n.4, p.425-439, Winter 1996
	Jun-Dong Cho , Salil Raje , Majid Sarrafzadeh, Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering for VLSI Applications, IEEE Transactions on Computers, v.47 n.11, p.1253-1266, November 1998
	W. R. Pulleyblank, Mathematical sciences in the nineties, IBM Journal of Research and Development, v.47 n.1, p.89-96, January 2003
	Surajit Chaudhuri , Mayur Datar , Vivek Narasayya, Index Selection for Databases: A Hardness Study and a Principled Heuristic Solution, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1313-1323, November 2004
	Gerald Gruber , Franz Rendl, Computational Experience with Ill-Posed Problems in Semidefinite Programming, Computational Optimization and Applications, v.21 n.2, p.201-212, February 2002
	Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Yaoyun Shi, Tensor norms and the classical communication complexity of nonlocal quantum measurement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Hoong Chuin Lau , Osamu Watanabe, Randomized approximations of the constraint satisfaction problem, Nordic Journal of Computing, v.3 n.4, p.405-424, Winter 1996
	B. Bollobás , A. D. Scott, Problems and results on judicious partitions, Random Structures & Algorithms, v.21 n.3-4, p.414-430, October 2002
	Mayur Datar , Tomás Feder , Aristides Gionis , Rajeev Motwani , Rina Panigrahy, A combinatorial algorithm for MAX CSP, Information Processing Letters, v.85 n.6, p.307-315, 31 March 2003
	Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Takao Asano, An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Theoretical Computer Science, v.354 n.3, p.339-353, 4 April 2006
	Eric Angel , Evripidis Bampis , Laurent Gourvès, Approximation algorithms for the bi-criteria weighted MAX-CUT problem, Discrete Applied Mathematics, v.154 n.12, p.1685-1692, 15 July 2006
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Hoong Chuin Lau, A New Approach for Weighted Constraint Satisfaction, Constraints, v.7 n.2, p.151-165, April 2002
	Anne Condon, Approximate solutions to problems in PSPACE, ACM SIGACT News, v.26 n.2, p.4-13, June 1995
	Naum Z. Shor , Petro I. Stetsyuk, Lagrangian bounds in multiextremal polynomial and discrete optimization problems, Journal of Global Optimization, v.23 n.1, p.1-41, May 2002
	Jin-Yi Cai, Holographic algorithms: guest column, ACM SIGACT News, v.39 n.2, June 2008
	Trip Denton , Ali Shokoufandeh , John Novatnack , Ko Nishino, Canonical subsets of image features, Computer Vision and Image Understanding, v.112 n.1, p.55-66, October, 2008
	Meena Mahajan , Venkatesh Raman , Somnath Sikdar, Parameterizing above or below guaranteed values, Journal of Computer and System Sciences, v.75 n.2, p.137-153, February, 2009
	Petros Drineas , Ravi Kannan , Michael W. Mahoney, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms, Random Structures & Algorithms, v.32 n.3, p.307-333, May 2008