Expander flows, geometric embeddings and graph partitioning

Expander flows, geometric embeddings and graph partitioning,10.1145/1502793.1502794,Journal of The ACM,Sanjeev Arora,Satish Rao,Umesh V. Vazirani

Expander flows, geometric embeddings and graph partitioning   (Citations: 20)
BibTex | RIS | RefWorks Download
We give a O(&sqrt;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 Rd, 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.
Journal: Journal of The ACM - JACM , vol. 56, no. 2, pp. 1-37, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: