Sanjeev Arora
Satish Rao
Umesh Vazirani
Skip Abstract Section
Abstract
We give a O(√log n)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in Rd, whose proof makes essential use of a phenomenon called measure concentration.
We also describe an interesting and natural “approximate certificate” for a graph's expansion, which involves embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.
- Agarwal, A., Charikar, M., Makarychev, K., and Makarychev, Y. 2005. o(&sqrt;log n) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems. In STOC '05: Proceedings of the 34th annual ACM Symposium on Theory of Computing. ACM, New York, 573--581. Google Scholar
Digital Library
- Alizadeh, F. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 1, 13--51.Google ScholarDigital Library
- Alon, N. 1986. Eigenvalues and expanders. Combinatorica 6, 2, 83--96. Google ScholarDigital Library
- Alon, N., and Milman, V. D. 1985. λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38, 1, 73--88.Google ScholarCross Ref
- Arora, S., Hazan, E., and Kale, S. 2004. 0(&sqrt; 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). IEEE Computer Society Press, Los Alamitos, CA, 238--247. Google ScholarDigital Library
- Arora, S., and Kale, S. 2007. A combinatorial, primal-dual approach to semidefinite programs. In STOC '07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. ACM, New York, 227--236. Google ScholarDigital Library
- Arora, S., Lee, J. R., and Naor, A. 2008. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc. 21, 1, 1--21 (electronic).Google ScholarCross Ref
- Aumann, Y., and Rabani, Y. 1998. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 1, 291--301 (electronic). Google ScholarDigital Library
- Ball, K. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry. Mathematics Science Research Institute Publisher, vol. 31. Cambridge Univ. Press, Cambridge, 1--58.Google Scholar
- Blum, M., Karp, R., Vornberger, O., Papadimitriou, C., and Yannakakis, M. 1981. The complexity of testing whether a graph is a superconcentrator. Inf. Proc. Letters 13, 164--167.Google ScholarCross Ref
- Charikar, M., Hajiaghayi, M. T., Karloff, H., and Rao, S. 2006. l22 spreading metrics for vertex ordering problems. In SODA '06: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. ACM, New York, 1018--1027. Google ScholarDigital Library
- Chawla, S., Gupta, A., and Räcke, H. 2005. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 102--111. Google ScholarDigital Library
- Cheeger, J. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Probl. Analysis, 195--199.Google Scholar
- Chung, F. R. K. 1997. Spectral graph theory. CBMS Regional Conference Series in Mathematics, vol. 92. Published for the Conference Board of the Mathematical Sciences, Washington, DC.Google Scholar
- Danzer, L., and Branko, G. 1962. On two problems of P. Erdos and V. L. Klee concerning convex bodies (in German). Math. Zeitschrift 79, 95--99.Google ScholarCross Ref
- Devanur, N., Khot, S., Saket, R., and Vishnoi, N. 2006. Integrality gaps for sparsest cut and minimum linear arrangement problems. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 537--546. Google ScholarDigital Library
- Diaconis, P., and Saloff-Coste, L. 1993. Comparison theorems for reversible markov chains. Ann. Appl. Prob. 3, 696--730.Google ScholarCross Ref
- Enflo, P. 1969. On the nonexistence of uniform homeomorphisms between Lp-spaces. Ark. Mat. 8, 103--105.Google ScholarCross Ref
- Feige, U., Hajiaghayi, M., and Lee, J. R. 2005. Improved approximation algorithms for minimum-weight vertex separators. In STOC '05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York, 563--572. Google ScholarDigital Library
- Feige, U., and Lee, J. R. 2007. An improved approximation ratio for the minimum linear arrangement problem. Inform. Process. Lett. 101, 1, 26--29. Google ScholarDigital Library
- Goemans, M. X. 1998. Semidefinite programming and combinatorial optimization. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Doc. Math., 657--666 (electronic).Google Scholar
- Goemans, M. X., and Williamson, D. P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6, 1115--1145. Google ScholarDigital Library
- Grötschel, M., Lovász, L., and Schrijver, A. 1993. Geometric algorithms and combinatorial optimization, Second ed. Algorithms and Combinatorics, vol. 2. Springer-Verlag, Berlin, Germany.Google Scholar
- Jerrum, M., and Sinclair, A. 1989. Approximating the permanent. SIAM J. Comput. 18, 6, 1149--1178. Google ScholarDigital Library
- Karakostas, G. 2005. A better approximation ratio for the vertex cover problem. In Automata, languages and programming. Lecture Notes in Computer Science vol. 3580. Springer-Verlag, Berlin, Germany, 1043--1050. Google ScholarDigital Library
- Karger, D., Motwani, R., and Sudan, M. 1998. Approximate graph coloring by semidefinite programming. J. ACM 45, 2, 246--265. Google ScholarDigital Library
- Karloff, H. J., and Zwick, U. 1997. A 7/8-approximation algorithm for max 3sat? In Proceedings of the 38th IEEE Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 406--415. Google ScholarDigital Library
- Khandekar, R., Rao, S., and Vazirani, U. 2006. Graph partitioning using single commodity flows. In STOC '06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 385--390. Google ScholarDigital Library
- Khot, S., and Vishnoi, N. 2005. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ1. In FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 53--62. Google ScholarDigital Library
- Krauthgamer, R., Lee, J. R., Mendel, M., and Naor, A. 2005. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15, 4, 839--858.Google ScholarCross Ref
- Krauthgamer, R., and Rabani, Y. 2006. Improved lower bounds for embeddings into l1. In SODA '06: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. ACM, New York, 1010--1017. Google ScholarDigital Library
- Lang, K., and Rao, S. 2004. A flow-based method for improving the expansion or conductance of graph cuts. In Proceedings of the 10th International IPCO Conference. Lecture Notes in Computer Science, vol. 3064. Springer-Verlag, Berlin, Germany, 325--337.Google Scholar
- Lee, J. R. 2005. On distance scales, embeddings, and efficient relaxations of the cut cone. In SODA '05: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, USA, 92--101. Google ScholarDigital Library
- Leighton, T., and Rao, S. 1999. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM 46, 6, 787--832. Google ScholarDigital Library
- Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--245.Google ScholarCross Ref
- Lovász, L., and Schrijver, A. 1991. Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 2, 166--190.Google ScholarDigital Library
- Matoušek, J. 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag, New York. Google ScholarDigital Library
- Naor, A., Rabani, Y., and Sinclair, A. 2005. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal. 227, 2, 273--303.Google ScholarCross Ref
- Nesterov, Y., and Nemirovskii, A. 1994. Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia, PA.Google Scholar
- Schechtman, G. 2003. Concentration, results and applications. In Handbook of the Geometry of Banach Spaces, volume 2, W. Johnson and J. Lindenstrauss, Eds. North Holland, Amsterdam, The Netherlands, (Draft version available from Schechtman's website).Google ScholarCross Ref
- Shahrokhi, F., and Matula, D. W. 1990. The maximum concurrent flow problem. J. Assoc. Comput. Mach. 37, 2, 318--334. Google ScholarDigital Library
- Sherali, H., and Adams, W. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3, 3, 411--430. Google ScholarDigital Library
- Shmoys, D. S. 1995. Cut problems and their application to divide and conquer. In Approximation Algorithms for NP-Hard Problems, D. Hochbaum, Ed. PWS Publishing. Google ScholarDigital Library
- Sinclair, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinat. Probab. Comput. 1, 4, 351--370.Google ScholarCross Ref
Index Terms
- Expander flows, geometric embeddings and graph partitioning
Recommendations
Expander flows, geometric embeddings and graph partitioning
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingWe give a O(√log n)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality ...
Improved Approximation Algorithms for Minimum Weight Vertex Separators
We develop the algorithmic theory of vertex separators and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into $L_1$ (and even Euclidean embeddings) are insufficient but that the additional ...
Partitioning a graph into small pieces with applications to path transversal
Given a graph $$G = (V, E)$$G=(V,E) and an integer $$k \in \mathbb {N}$$kýN, we study $$k$$k-Vertex Separator (resp. $$k$$k-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in ...
Comments