Expander flows, geometric embeddings and graph partitioning

ABSTRACT

We give a O(&sqrt;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 R^d, 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.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Alizadeh, F. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 1, 13--51.
• 3: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 4: Alon, N., and Milman, V. D. 1985. λ₁, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38, 1, 73--88.
• 5: 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]
• 6: 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]
• 7: Arora, S., Lee, J. R., and Naor, A. 2008. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc. 21, 1, 1--21 (electronic).
• 8: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 9: 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.
• 10: 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.
• 11: Moses Charikar , Mohammad Taghi Hajiaghayi , Howard Karloff , Satish Rao, l²₂ spreading metrics for vertex ordering problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1018-1027, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109670]
• 12: 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
• 13: Cheeger, J. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Probl. Analysis, 195--199.
• 14: 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.
• 15: 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.
• 16: Nikhil R. Devanur , Subhash A. Khot , Rishi Saket , Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132594]
• 17: Diaconis, P., and Saloff-Coste, L. 1993. Comparison theorems for reversible markov chains. Ann. Appl. Prob. 3, 696--730.
• 18: Enflo, P. 1969. On the nonexistence of uniform homeomorphisms between L_p-spaces. Ark. Mat. 8, 103--105.
• 19: Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060674]
• 20: Uriel Feige , James R. Lee, An improved approximation ratio for the minimum linear arrangement problem, Information Processing Letters, v.101 n.1, p.26-29, 16 January 2007 [doi>10.1016/j.ipl.2006.07.009]
• 21: 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).
• 22: 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]
• 23: 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.
• 24: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 25: 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.
• 26: David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
• 27: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.406, October 19-22, 1997
• 28: 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]
• 29: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 30: 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.
• 31: Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
• 32: 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.
• 33: 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
• 34: 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]
• 35: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--245.
• 36: Lovász, L., and Schrijver, A. 1991. Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 2, 166--190.
• 37: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 38: 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.
• 39: Nesterov, Y., and Nemirovskii, A. 1994. Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia, PA.
• 40: 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).
• 41: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 42: Hanif D. Sherali , Warren P. Adams, A hierarchy of relaxation between the continuous and convex hull representations, SIAM Journal on Discrete Mathematics, v.3 n.3, p.411-430, Aug. 1990 [doi>10.1137/0403036]
• 43: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 44: Sinclair, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinat. Probab. Comput. 1, 4, 351--370.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
Graph partitioning, expanders, expansion, graph separators, multicommodity flows, semidefinite programs