Article

Expander flows, geometric embeddings and graph partitioning

Authors:

Umesh VaziraniAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 222 - 231

https://doi.org/10.1145/1007352.1007355

Published: 13 June 2004 Publication History

Abstract

We 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 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 "certificate" for a graph's expansion, by embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.

References

[1]

F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optimization, 5:13--51, 1995.

[2]

N. Alon. Eigenvalues and expanders. Combinatorica 6:83--96, 1986.

Digital Library

[3]

N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory B 38:73--88, 1985.

[4]

Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithms. SIAM J. Comp

Digital Library

[5]

K. Ball. An elementary introduction to modern convex geometry, in Flavors of Geometry, S. Levy (ed. ), Cambridge University Press, 1997.

[6]

M. Blum, R. Karp, O. Vornberger, C. Papadimitriou, M. Yannakakis. The complexity of testing whether a graph is a superconcentrator. Inf. Proc. Letters 13:164--167, 1981.

[7]

J. Bourgain. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Mathematics 52:46--52, 1985.

[8]

J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian, in Problem in Analysis, 195-199, Princeton Univ. Press, (1970),

[9]

F. Chen, L. Lovasz and I. Pak. Lifting Markov Chains to Speed up Mixing. Proc. ACM STOC, 1999, pp 275--281.

Digital Library

[10]

F. Chung. Spectral graph theory. CBMS Regional Conference Series in Mathematics, 92, American Mathematical Society, 1997.

[11]

L. Danzer and B. Grunbaum. On two problems of P. Erdos and V. L. Klee concerning convex bodies (in German). Math. Zeitschrift 79:95--99, 1962.

[12]

P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains. Annals of Applied Probability, 3:696--730, 1993.

[13]

U. Feige and R. Krauthgamer. A polylogarithmic approximation of the minimum bisection. In IEEE FOCS 2001 pp 105--115.

Digital Library

[14]

N. Garg and J. Koneman. Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems. In IEEE FOCS 1997.

Digital Library

[15]

N. Garg and V. V. Vazirani and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Computing, 25(2):235--251, 1996. Prelim. version in Proc. ACM STOC'93.

Digital Library

[16]

M. X. Goemans. Semidefinite programming in combinatorial optimization. Math. Programming, 79:143--161, 1997.

Digital Library

[17]

M. X. Goemans. unpublished note.

[18]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM, 42(6):1115--1145, 1995.

Digital Library

[19]

M. Grotschel, L. Lovasz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, 1993.

[20]

H. Karloff and U. Zwick. A 7/8-approximation algorithm for MAX 3SAT? Proc. of 38th IEEE FOCS (1997), 406-415.

Digital Library

[21]

D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. JACM, 45(2):246--265, 1998.

Digital Library

[22]

M. Jerrum and A. Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989.

Digital Library

[23]

T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM 46 1999. Prelim. version in ACM STOC 1988.

Digital Library

[24]

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica 15:215--246, 1995.

[25]

L. Lovasz. On the Shannon capacity of a graph. IEEE Trans. on Info. Theory IT-25:1--7, 1979.

Digital Library

[26]

A. Lubotzky, R. Philips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--277, 1988.

[27]

J. Matousek. Lectures on Discrete Geometry. Springer Verlag, 2002.

Digital Library

[28]

Y. Nesterov and A. Nemirovskii. Interior point polynomial methods in convex programming. SIAM, Philadelphia, PA 1994.

[29]

S. Plotkin and D. B. Shmoys and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Operations Res. 20:257--301, 1995. Prelim. version IEEE Foundations of Computer Science, 1991, 495--504.

Digital Library

[30]

G. Schechtman. Concentration, results and applications. Handbook of the Geometry of Banach Spaces, volume 2, W. B. Johnson and J. Lindenstrauss (eds. ), North Holland, 2003. Draft version available from Schechtman's website.

[31]

F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Journal of the ACM, 37:318--334, 1990.

Digital Library

[32]

D. S. Shmoys. Cut problems and their application to divide and conquer. Approximation Algorithms for NP-hard problems, D. S. Hochbaum (ed. ), PWS Publishing, 1995.

Digital Library

[33]

A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Prob., Comput. 1:351--370, 1992.

[34]

V. Vazirani. Approximation algorithms. Springer Verlag, 2002.

Digital Library

[35]

K. Zatloukal. Personal communication, November 2003.

Cited By

Ning BGao Y(2025)Efficient Partitioning Algorithms for Optimizing Big Graph ComputationComputing and Combinatorics10.1007/978-981-96-1093-8_17(202-213)Online publication date: 20-Feb-2025
https://doi.org/10.1007/978-981-96-1093-8_17
Cohen-Addad Vd'Orsi TMousavifar ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A near-linear time approximation algorithm for beyond-worst-case graph clusteringProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692437(9208-9229)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692437
Wu LRen X(2023)Optimal Bond Percolation in Networks by a Fast-Decycling FrameworkComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_40(509-519)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-21131-7_40
Show More Cited By

Index Terms

Expander flows, geometric embeddings and graph partitioning
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Expander flows, geometric embeddings and graph partitioning

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 ...
An Expander-Based Approach to Geometric Optimization

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric-searching technique of Megiddo [J. ACM, 30 (1983), pp. 852--865]. Our new approach is based on expander graphs and range-searching ...
Splitting an Expander Graph

Let G=(V,E) be an r-regular expander graph. Certain algorithms for finding edge disjoint paths require that its edges be partitioned into E=E1 E2 Ek so that the graphs Gi=(V,Ei) are each expanders. In this paper we give a nonconstructive proof of the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

259
Total Citations
View Citations
1,200
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ning BGao Y(2025)Efficient Partitioning Algorithms for Optimizing Big Graph ComputationComputing and Combinatorics10.1007/978-981-96-1093-8_17(202-213)Online publication date: 20-Feb-2025
https://doi.org/10.1007/978-981-96-1093-8_17
Cohen-Addad Vd'Orsi TMousavifar ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A near-linear time approximation algorithm for beyond-worst-case graph clusteringProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692437(9208-9229)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692437
Wu LRen X(2023)Optimal Bond Percolation in Networks by a Fast-Decycling FrameworkComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_40(509-519)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-21131-7_40
Chen YWang BWang XLee JPetrank E(2021)Extending MapReduce framework with locality keysProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441607(460-462)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441607
Gilani ZFarahbakhsh RTyson GCrowcroft J(2019)A Large-scale Behavioural Analysis of Bots and Humans on TwitterACM Transactions on the Web10.1145/329878913:1(1-23)Online publication date: 5-Feb-2019
https://dl.acm.org/doi/10.1145/3298789
Romero DUzzi BKleinberg J(2019)Social Networks under StressACM Transactions on the Web10.1145/329546013:1(1-24)Online publication date: 8-Feb-2019
https://dl.acm.org/doi/10.1145/3295460
Ren XAntulov-Fantulin N(2019)Ensemble Approach for Generalized Network DismantlingComplex Networks and Their Applications VIII10.1007/978-3-030-36687-2_65(783-793)Online publication date: 26-Nov-2019
https://doi.org/10.1007/978-3-030-36687-2_65
Zhao ZZheng SLi CSun JChang LChiclana F(2018)A comparative study on community detection methods in complex networksJournal of Intelligent & Fuzzy Systems10.3233/JIFS-1768235:1(1077-1086)Online publication date: 27-Jul-2018
https://doi.org/10.3233/JIFS-17682
Räcke HSchwartz RStotz RScheideler CFineman J(2018)Trees for Vertex Cuts, Hypergraph Cuts and Minimum Hypergraph BisectionProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210398(23-32)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210398
Hopkins SKothari PPotechin ARaghavendra PSchramm T(2018)On the Integrality Gap of Degree-4 Sum of Squares for Planted CliqueACM Transactions on Algorithms10.1145/317853814:3(1-31)Online publication date: 16-Jun-2018
https://dl.acm.org/doi/10.1145/3178538
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten