Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora; Satish Rao; Umesh Vazirani

doi:10.1145/1007352.1007355

Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora, Satish Rao, Umesh Vazirani

Research output: Contribution to journal › Conference article › peer-review

240 Scopus citations

Abstract

We give a O(√log n)-approximation algorithm for SPARS-EST 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 ℜ^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.

Original language	English (US)
Pages (from-to)	222-231
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1007352.1007355
State	Published - 2004
Event	Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation algorithms
Clustering
Conductance
Eigenvalues
Embedding
Expander
Graph partitioning
Normalized cuts
Semidefinite programming
Sparsest cuts
Spectral methods

Access to Document

10.1145/1007352.1007355

Cite this

@article{3b0ea076eeb84a18998cf1fb398ff6f6,

title = "Expander flows, geometric embeddings and graph partitioning",

abstract = "We give a O(√log n)-approximation algorithm for SPARS-EST 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 ℜ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.",

keywords = "Approximation algorithms, Clustering, Conductance, Eigenvalues, Embedding, Expander, Graph partitioning, Normalized cuts, Semidefinite programming, Sparsest cuts, Spectral methods",

author = "Sanjeev Arora and Satish Rao and Umesh Vazirani",

year = "2004",

doi = "10.1145/1007352.1007355",

language = "English (US)",

pages = "222--231",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 36th Annual ACM Symposium on Theory of Computing ; Conference date: 13-06-2004 Through 15-06-2004",

}

TY - JOUR

T1 - Expander flows, geometric embeddings and graph partitioning

AU - Arora, Sanjeev

AU - Rao, Satish

AU - Vazirani, Umesh

PY - 2004

Y1 - 2004

N2 - We give a O(√log n)-approximation algorithm for SPARS-EST 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 ℜ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.

AB - We give a O(√log n)-approximation algorithm for SPARS-EST 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 ℜ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.

KW - Approximation algorithms

KW - Clustering

KW - Conductance

KW - Eigenvalues

KW - Embedding

KW - Expander

KW - Graph partitioning

KW - Normalized cuts

KW - Semidefinite programming

KW - Sparsest cuts

KW - Spectral methods

UR - http://www.scopus.com/inward/record.url?scp=4544250512&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4544250512&partnerID=8YFLogxK

U2 - 10.1145/1007352.1007355

DO - 10.1145/1007352.1007355

M3 - Conference article

AN - SCOPUS:4544250512

SN - 0734-9025

SP - 222

EP - 231

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 36th Annual ACM Symposium on Theory of Computing

Y2 - 13 June 2004 through 15 June 2004

ER -

Expander flows, geometric embeddings and graph partitioning

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this