Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora, Satish Rao, Umesh Vazirani

Research output: Contribution to journalConference articlepeer-review

227 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 languageEnglish (US)
Pages (from-to)222-231
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2004
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 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

Fingerprint Dive into the research topics of 'Expander flows, geometric embeddings and graph partitioning'. Together they form a unique fingerprint.

Cite this