pith. sign in

arxiv: 1304.3365 · v1 · pith:ARPKGQHAnew · submitted 2013-04-11 · 💻 cs.DS · cs.CC

Towards a better approximation for sparsest cut?

classification 💻 cs.DS cs.CC
keywords approximationalgorithmsgraphssmallsparsestconditionepsilonexpand
0
0 comments X
read the original abstract

We give a new $(1+\epsilon)$-approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size $n/r$ expand by a factor $\sqrt{\log n\log r}$ bigger, 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 {\em Small Set Expander Flows} (inspired by the {\em expander flows} of ARV) which we show exists in the input graph. Both algorithms run in time $2^{O(r)} \mathrm{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+\epsilon)$-approximation on such general family of graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.