### Abstract

We give a O(√log n)-approximation algorithm for SPARS-EST CUT, 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 "certificate" for a graph's expansion, by embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.

Original language | English (US) |
---|---|

Pages (from-to) | 222-231 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - Jan 1 2004 |

Event | Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Approximation algorithms
- Clustering
- Conductance
- Eigenvalues
- Embedding
- Expander
- Graph partitioning
- Normalized cuts
- Semidefinite programming
- Sparsest cuts
- Spectral methods

## Fingerprint Dive into the research topics of 'Expander flows, geometric embeddings and graph partitioning'. Together they form a unique fingerprint.

## Cite this

Arora, S., Rao, S., & Vazirani, U. (2004). Expander flows, geometric embeddings and graph partitioning.

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 222-231. https://doi.org/10.1145/1007352.1007355