Towards a Better Approximation for Sparsest Cut?

摘要

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 nlog 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 [ARV'09] 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.