Journal
JOURNAL OF THE ACM
Volume 56, Issue 2, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1502793.1502794
Keywords
Algorithms; Theory; Graph partitioning; semidefinite programs; graph separators; multicommodity flows; expansion; expanders
Ask authors/readers for more resources
We give a O(root 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available