Skip to main content

Towards a better approximation for SPARSEST CUT?

Author(s): Arora, Sanjeev; Ge, R; Sinop, AK

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1ct7h
Abstract: We give a new (1 + ε)-approximation for SPARSEST CUT problem on graphs where small sets expand significantly more than the sparsest cut (expansion of sets of size n/r exceeds that of the sparsest cut by a factor √ log n log r, for some small r; this condition holds for many natural graph families). We give two different algorithms. One involves Guruswami-Sinop rounding on the level-r Lasserre relaxation. The other is combinatorial and involves a new notion called Small Set Expander Flows (inspired by the expander flows of [1]) which we show exists in the input graph. Both algorithms run in time 2O(r)poly(n). We also show similar approximation algorithms in graphs with genus g with an analogous local expansion condition. This is the first algorithm we know of that achieves (1 + ε)-approximation on such general family of graphs.
Publication Date: 2013
Citation: Arora, S, Ge, R, Sinop, AK. (2013). Towards a better approximation for SPARSEST CUT?. 270 - 279. doi:10.1109/FOCS.2013.37
DOI: doi:10.1109/FOCS.2013.37
Pages: 270 - 279
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.