turns out to be equal to the distortion required to embed
l2 metrics into l . The embeddings of5, 7 actually embed
21
l 2 into l (which in turn embeds with no distortion into l ),
2 2 O ( log n loglog n ) 1 thus implying an approximation algorithm for this general form of graph partitioning.
acknowledgments
This work was supported by NSF grants MSPA-MCS 0528414,
CCF 0514993, ITR 0205594, CCF-0515304, CCF-0635357,
CCF-0635401 and ITR CCR-0121555.
References
1. Alon, N. Eigenvalues and expanders.
Combinatorica, 6( 2): 83–96, 1986.
2. Arora, S., Hazan, E., and Kale, S.
O log n approximation to sparsest
cut in Õ(n2) time. In FOCS ‘04:
Proceedings of the 45th Annual
IEEE Symposium on Foundations of
Computer Science (FOCS’04), pages
238–247, Washington, DC, USA,
2004. IEEE Computer Society.
3. Arora, S., Hazan, E., and Kale, S.
Multiplicative weights method:
a meta-algorithm and its
applications—a survey, 2005.
4. Arora, S. and Kale, S. A
combinatorial, primal-dual approach
to semidefinite programs. In STOC
‘07: Proceedings of the Thirty-Ninth
Annual ACM Symposium on Theory
of Computing, pages 227–236, New
York, NY, USA, 2007. ACM.
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. Arora, S., Rao, S., and Vazirani,
U. Expander flows, geometric
embeddings and graph partitioning.
In STOC ‘04: Proceedings of the
Thirty-Sixth Annual ACM Symposium
on Theory of Computing, pages
222–231, New York, N Y, USA, 2004.
ACM.
7. Chawla, S., Gupta, A., and Raecke, H.
Embeddings of negative-type metrics
and an improved approximation
to generalized sparsest cut. In
SODA ‘05: Proceedings of the
Sixteenth Annual ACM-SIAM
Symposium on Discrete Algorithms,
pages 102–111, Philadelphia, PA,
USA, 2005. Society for Industrial
and Applied Mathematics.
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. III (Berlin,
1998), pages 657–666, 1998
(electronic).
10. Goemans, M. X. and Williamson,
D. P. Improved approximation
algorithms for maximum cut
and satisfiability problems using
Sanjeev Arora ( arora@cs.princeton.edu)
Computer Science Department,
Princeton University,
Princeton, NJ 08544, USA
Satish Rao ( satishr@cs.berkeley.edu)
Computer Science Department, UC,
Berkeley, CA 94720, USA
© 2008 ACM 0001-0782/08/1000 $5.00
semidefinite programming. J. Assoc.
Comput. Mach., 42( 6):1115–1145,
1995.
11. Karypis, G. and Kumar, V. A fast and
high quality multilevel scheme for
partitioning irregular graphs. SIAM
J. Scientific Comput., 20( 1):359–392,
1998.
12. Khandekar, R., Rao, S., and Vazirani,
U. Graph partitioning using single
commodity flows. In STOC ‘06:
Proceedings of the Thirty-Eighth
Annual ACM Symposium on
Theory of Computing, pages
385–390, New York, NY, USA, 2006.
ACM Press.
13. Lee, J. R. On distance scales,
embeddings, and efficient relaxations
of the cut cone. In SODA ‘05:
Proceedings of the Sixteenth
Annual ACM-SIAM Symposium
on Discrete Algorithms, pages
92–101, Philadelphia, PA, USA, 2005.
Society for Industrial and Applied
Mathematics.
14. Leighton, T. and Rao, S.
Multicommodity max-flow min-cut
theorems and their use in designing
approximation algorithms. J. ACM
(JACM), 46( 6):787–832, 1999.
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. Orecchia, L., Schulman, L. Vazirani,
U., and Vishnoin, N. On partitioning
graphs via single commodity
flows. In Proceedings of the 40th
Annual ACM Symposium on Theory
of Computing, Victoria, British
Columbia, Canada, May 17–20, 2008,
pages 461–470, 2008.
17. Shmoys, D. S. Cut problems and their
application to divide and conquer. In
D. S. Hochbaum, ed., Approximation
Algorithms for NP-Hard Problems.
PWS Publishing, 1995.
18. Sinclair, A. and Jerrum, M.
Approximate counting, uniform
generation and rapidly mixing
Markov chains (extended abstract).
In Graph-Theoretic Concepts in
Computer Science (Staffelstein,
1987), volume 314 of Lecture Notes
in Comput. Sci., pages 134–148,
Berlin, 1988. Springer.
Umesh Vazirani (vazirani@cs.
berkeley.edu) Computer Science
Department, UC, Berkeley,
CA 94720, USA
A previous version of this paper, entitled
“Expander Flows, Geometric Embeddings,
and Graph Partitioning,” was published
in Proceedings of the 36th Annual
Symposium on the Theory of Computing
(Chicago, June 13–16, 2004).
ACM
Transactions On
Asian Language
Information
Processing
The Asian Language Information Processing
Transaction (TALIP) publishes high quality original
archival papers and technical notes in the areas of
computation and processing of information in Asian
languages and related disciplines. Some of the
subjects to be covered by this quarterly publication
are: Computational Linguistics; Linguistic Resources;
Hardware and Software Algorithms and Tools for
Asian Language Processing; Machine Translation; and
Multimedia Asian Information Processing. Emphasis
will be placed on the originality and the practical
significance of the reported research.
To learn more about TALIP, please visit
www.acm.org/pubs/talip/
SUBSCRIBE TODAY!
PRODUCT INFORMATION
ISSN: 1530-0226
Order Code: 138
Price: $38 Professional Member
$33 Student Member
$160 Non-Member
$16 Air Service (for residents
outside North America only)
TO PLACE AN ORDER
Contact ACM Member Services
Phone: 1.800.342.6626 (U.S. and Canada)
+ 1.212.626.0500 (Global)
Fax: + 1.212.944.1318
(Hours: 8:30am—4:30pm, Eastern Time)
Email: acmhelp@acm.org
Mail: ACM Member Services
General Post Office
PO Box 30777
New York, NY 10087-0777 USA
www.acm.org/pubs/talip/
AD28