Loading...
Please wait, while we are loading the content...
Similar Documents
Expander flows, geometric embeddings and graph partitioning (2009).
| Content Provider | CiteSeerX |
|---|---|
| Author | Arora, Sanjeev Rao, Satish Vazirani, Umesh |
| Abstract | We give a O(√ 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 ℜ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. |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Expander Flow Geometric Embeddings Graph Partitioning Edge Expansion Triangle Inequality Constraint Well-known Semidefinite Relaxation Graph Expansion Appropriate Dilation Point Set Measure Concentration Sparsest Cut Essential Use Approximation Algorithm N-node Expander Graph Conductance Problem Geometric Theorem Balanced Separator Natural Approximate Certificate |
| Content Type | Text |
