### 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 - Feb 25 2010 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

### Keywords

- Expander flows
- Graph partitioning
- Multiplicative weights

## Fingerprint Dive into the research topics of 'O(√log n) approximation to sparsest cut in õ(n<sup>2</sup>) time'. Together they form a unique fingerprint.

## Cite this

Arora, S., Hazan, E., & Kale, S. (2010). O(√log n) approximation to sparsest cut in õ(n

^{2}) time.*SIAM Journal on Computing*,*39*(5), 1748-1771. https://doi.org/10.1137/080731049