## 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 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.

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

Article number | 5 |

Journal | Journal of the ACM |

Volume | 56 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 2009 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Expanders
- Expansion
- Graph partitioning
- Graph separators
- Multicommodity flows
- Semidefinite programs