TY - GEN

T1 - Towards a better approximation for SPARSEST CUT?

AU - Arora, Sanjeev

AU - Ge, Rong

AU - Sinop, Ali Kemal

PY - 2013/12/1

Y1 - 2013/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84893460451&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893460451&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2013.37

DO - 10.1109/FOCS.2013.37

M3 - Conference contribution

AN - SCOPUS:84893460451

SN - 9780769551357

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

SP - 270

EP - 279

BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

Y2 - 27 October 2013 through 29 October 2013

ER -