Communications - October 2008

turns out to be equal to the distortion required to embed l²metrics into l . The embeddings of^{5, 7}actually embed 21 l ² into l (which in turn embeds with no distortion into l ), ²²O ( log n loglog n ) ¹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 Õ(n²) 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

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.