### Expander flows, geometric embeddings and graph partitioningExpander flows, geometric embeddings and graph partitioning

Access Restriction
Subscribed

 Author Arora, Sanjeev ♦ Rao, Satish ♦ Vazirani, Umesh Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Graph partitioning ♦ Expanders ♦ Expansion ♦ Graph separators ♦ Multicommodity flows ♦ Semidefinite programs Abstract We give a $\textit{O}(&sqrt;log$ $\textit{n})-approximation$ algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the $\textit{O}(log$ $\textit{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 $\textit{n}-node$ expander in it with appropriate dilation and congestion. We call this an expander flow. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 2 Page Count 37 Starting Page 1 Ending Page 37

#### Open content in new tab

Source: ACM Digital Library