Access Restriction

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

   Open content in new tab
Source: ACM Digital Library