Geometry, flows, and graph-partitioning algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometry, flows, and graph-partitioning algorithms

Full text

Digital Edition , Html

Html (1 KB), Pdf

Pdf (827 KB)

Source

Communications of the ACM archive
Volume 51 , Issue 10 (October 2008) table of contents
The many facets of natural computing

SECTION: Research highlights table of contents

Pages 96-105

Year of Publication: 2008

ISSN:0001-0782

Authors

Sanjeev Arora	Princeton University, Princeton, NJ
Satish Rao	UC, Berkeley, CA
Umesh Vazirani	UC, Berkeley, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 389, Citation Count: 0

Additional Information:

references 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/1400181.1400204 What is a DOI?

Warning: The download time has expired please click on the item to try again.

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	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	2	Sanjeev Arora , Elad Hazan , Satyen Kale, 0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.238-247, October 17-19, 2004 [doi>10.1109/FOCS.2004.1]
	3	Arora, S., Hazan, E., and Kale, S. Multiplicative weights method: a meta-algorithm and its applications---a survey, 2005.
	4	Sanjeev Arora , Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250823]
	5	Arora, S., Lee, J. R., and Naor, A. Euclidean distortion and the sparsest cut. J. Amer Math, Soc., 21(1):1--21 2008 (Electronic).
	6	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
	7	Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	8	Cheeger, J. A lower bound for the smallest eigenvalue of the Laplacian. In Problem in Analysis, pages 195--199, 1970.
	9	Goemans, M. X. Semidefinite programming and combinatorial optimization. In Proceedings of the International Congress of Mathematicians, Vol. Ill (Berlin, 1998), pages 657--666,1998 (electronic).
	10	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]
	11	George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
	12	Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132574]
	13	James R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	14	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
	15	Linial, N., London, E., and Rabinovich, Y. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
	16	Lorenzo Orecchia , Leonard J. Schulman , Umesh V. Vazirani , Nisheeth K. Vishnoi, On partitioning graphs via single commodity flows, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374442]
	17	David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	18	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains (extended abstract), Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.134-148, July 1988, Kloster Banz/Staffelstein, Germany