Outward rotations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems

Full text

Pdf (714 KB)

Source

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

Atlanta, Georgia, United States

Pages: 679 - 687

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Uri Zwick

Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 30, Citation Count: 32

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

	AE98	Gunnar Andersson , Lars Engebretsen, Better approximation algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT, Information Processing Letters, v.65 n.6, p.305-311, March 27, 1998 [doi>10.1016/S0020-0190(98)00021-0]
	AL97	Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	AS98	N. Alon and B. Sudakov. Bipartite subgraphs and the smallest eigenvalue. Manuscript, 1998.
	Asa97	Takao Asano, Approximation Algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.24, June 17-19, 1997
	ASZ98	N. Alon, B. Sudakov, and U. Zwick. Work in progress, 1998.
	FG95	Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
	GW95	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]
	Hås97	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 [doi>10.1145/258533.258536]
	HZ99	Eran Halperin , Uri Zwick, Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.202-217, June 09-11, 1999
	Kar96	Howard Karloff, How good is the Goemans-Williamson MAX CUT algorithm?, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.427-434, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237990]
	KLP96	Viggo Kann , Jens Lagergren , Alessandro Panconesi, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Information Processing Letters, v.58 n.3, p.105-110, May 13, 1996 [doi>10.1016/0020-0190(96)00046-4]
	KZ97	Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
	MR95	S. Mahajan , H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.162, October 23-25, 1995
	Nes98	Y.E. Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 9:141-160, 1998.
	Tre97	Luca Trevisan, Approximating Satisfiable Satisfiability Problems (Extended Abstract), Proceedings of the 5th Annual European Symposium on Algorithms, p.472-485, September 15-17, 1997
	Yan94	Mihalis Yannakakis, On the approximation of maximum satisfiability, Journal of Algorithms, v.17 n.3, p.475-502, Nov. 1994
	Zwi98a	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
	Zwi98b	Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276869]

CITED BY 32

	Noga Alon , Benny Sudakov , Uri Zwick, Constructing worst case instances for semidefinite programming based approximation algorithms, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.92-100, January 07-09, 2001, Washington, D.C., United States
	Michel X. Goemans , David Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.443-452, July 2001, Hersonissos, Greece
	Uri Zwick, Computer assisted proof of optimal approximability results, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.496-505, January 06-08, 2002, San Francisco, California
	Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	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
	Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
	Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.506-513, January 06-08, 2002, San Francisco, California
	Eran Halperin , Uri Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures & Algorithms, v.20 n.3, p.382-402, May 2002
	Heng Yang , Yinyu Ye , Jiawei Zhang, An approximation algorithm for scheduling two parallel machines with capacity constraints, Discrete Applied Mathematics, v.130 n.3, p.449-467, 23 August 2003
	Bernard Chazelle , Carl Kingsford , Mona Singh, The side-chain positioning problem: a semidefinite programming formulation with new rounding schemes, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.86-94, June 08-08, 2003, San Diego, California, USA
	Michel X. Goemans , David P. Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Journal of Computer and System Sciences, v.68 n.2, p.442-470, March 2004
	Noga Alon , Assaf Naor, Approximating the cut-norm via Grothendieck's inequality, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Journal of Algorithms, v.53 n.2, p.169-185, November 2004
	Lars Engebretsen , Venkatesan Guruswami, Is constraint satisfaction over two variables always easy?, Random Structures & Algorithms, v.25 n.2, p.150-178, September 2004
	Johan Håstad, Every 2-CSP allows nontrivial approximation, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ali Shokoufandeh , Spiros Mancoridis , Trip Denton , Matthew Maycock, Spectral and meta-heuristic algorithms for software clustering, Journal of Systems and Software, v.77 n.3, p.213-223, September 2005
	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
	Amin Coja-Oghlan , Cristopher Moore , Vishal Sanwalani, MAX k-CUT and approximating the chromatic number of random graphs, Random Structures & Algorithms, v.28 n.3, p.289-322, May 2006
	Uriel Feige , Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut, Random Structures & Algorithms, v.20 n.3, p.403-440, May 2002
	Uriel Feige , Michael Langberg, The RPR² rounding technique for semidefinite programs, Journal of Algorithms, v.60 n.1, p.1-23, July 2006
	Ryan O'Donnell, Some topics in analysis of boolean functions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Bernard Chazelle , Carl Kingsford , Mona Singh, A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies, INFORMS Journal on Computing, v.16 n.4, p.380-392, Fall 2004
	Hernán Alperin , Ivo Nowak, Lagrangian Smoothing Heuristics for Max-Cut, Journal of Heuristics, v.11 n.5-6, p.447-463, December 2005
	Yinyu Ye , Jiawei Zhang, Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection, Journal of Global Optimization, v.25 n.1, p.55-73, January 2003
	E. de Klerk , H. van Maaren, On Semidefinite Programming Relaxations of (2+p)-SAT, Annals of Mathematics and Artificial Intelligence, v.37 n.3, p.285-305, March 2003
	Dachuan Xu , Jiye Han , Zhenghai Huang , Liping Zhang, Improved Approximation Algorithms for MAX $\frac{n}2$ -DIRECTED-BISECTION and MAX $\frac{n}2$ -DENSE-SUBGRAPH, Journal of Global Optimization, v.27 n.4, p.399-410, December 2003
	Ryan O'Donnell , Yi Wu, An optimal sdp algorithm for max-cut, and equally optimal long code tests, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Robert Cimikowski , Brendan Mumey, Approximating the fixed linear crossing number, Discrete Applied Mathematics, v.155 n.17, p.2202-2210, October, 2007
	M. Pawan Kumar , P. H. S. Torr, Efficiently solving convex relaxations for MAP estimation, Proceedings of the 25th international conference on Machine learning, p.680-687, July 05-09, 2008, Helsinki, Finland
	Ai-Fan Ling , Cheng-Xian Xu , Feng-Min Xu, A discrete filled function algorithm for approximate global solutions of max-cut problems, Journal of Computational and Applied Mathematics, v.220 n.1-2, p.643-660, October, 2008