## Abstract

This paper shows how to compute O(√log n)-approximations to the sparsest Cut and Balanced Separator problems in Õ(n^{2}) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 336th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ(n^{9.5})time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231].

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

Pages (from-to) | 1748-1771 |

Number of pages | 24 |

Journal | SIAM Journal on Computing |

Volume | 39 |

Issue number | 5 |

DOIs | |

State | Published - 2010 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Expander flows
- Graph partitioning
- Multiplicative weights

## Fingerprint

Dive into the research topics of 'O(√log n) approximation to sparsest cut in õ(n^{2}) time'. Together they form a unique fingerprint.