Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora, Satish Rao, Umesh Vazirani

Research output: Contribution to journalArticlepeer-review

342 Scopus citations

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 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.

Original languageEnglish (US)
Article number5
JournalJournal of the ACM
Volume56
Issue number2
DOIs
StatePublished - Apr 1 2009

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Expanders
  • Expansion
  • Graph partitioning
  • Graph separators
  • Multicommodity flows
  • Semidefinite programs

Fingerprint

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

Cite this