Expander flows, geometric embeddings and graph partitioning

Authors:
Top Cited Papers
Open Access
Publisher website
Google Scholar
Abstract
We give aO(√logn)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves theO(logn)-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 inRd, 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 ann-node expander in it with appropriate dilation and congestion. We call this an expander flow.
Funding Information
  • Division of Computing and Communication Foundations (CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357)
  • National Science Foundation (CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357, CCR-0121555)

This publication has 35 references indexed in Scilit: