Title: Towards a better approximation for Sparsest Cut?
Speaker: Ali Kemal Sinop, Princeton University
Date: Wednesday, May 1, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give a new $(1+eps)$-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 diff?erent 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 [ARV09]) which we show exists in the input graph. Both algorithms run in time $2^{O(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+\eps)$-approximation on such general family of graphs.
Joint work with Sanjeev Arora and Rong Ge.