Skip to main content

Towards a better approximation for SPARSEST CUT?

Publication ,  Journal Article
Arora, S; Ge, R; Sinop, AK
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
December 1, 2013

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. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Duke Scholars

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

December 1, 2013

Start / End Page

270 / 279
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arora, S., Ge, R., & Sinop, A. K. (2013). Towards a better approximation for SPARSEST CUT? Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 270–279. https://doi.org/10.1109/FOCS.2013.37
Arora, S., R. Ge, and A. K. Sinop. “Towards a better approximation for SPARSEST CUT?Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, December 1, 2013, 270–79. https://doi.org/10.1109/FOCS.2013.37.
Arora S, Ge R, Sinop AK. Towards a better approximation for SPARSEST CUT? Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2013 Dec 1;270–9.
Arora, S., et al. “Towards a better approximation for SPARSEST CUT?Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Dec. 2013, pp. 270–79. Scopus, doi:10.1109/FOCS.2013.37.
Arora S, Ge R, Sinop AK. Towards a better approximation for SPARSEST CUT? Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2013 Dec 1;270–279.

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

December 1, 2013

Start / End Page

270 / 279