Abstract: We consider approximation algorithms for the sparsest cut graph partitioning problem. Here, given graphs G with demand pairs $\{s_i,t_i\}$, the goal is to separate G into two parts to minimize the ratio of the number of edges cut to the number of demand pairs separated.
In this talk, I will sketch:
- the best hardness-of-approximation (based on P!=NP) currently known for this problem,
- and a 2-approximation algorithm with running time $n^{O(k)}$, where $k$ is the treewidth of the underlying graph G. Our algorithm rounds a Sherali-Adams LP relaxation.
This positive result can be complemented by (a) an integrality gap of a factor of 2 for the Sherali-Adams hierarchy even after polynomially
many rounds, and (b) an unique-games hardness of a factor of 2. Time permitting, I will give a high-level intuition of how the NP-hardness
can be extended to prove these matching results.
I will try to keep the talk as self-contained as possible (this is joint work with Kunal Talwar (Microsoft Research SVC) and David Witmer (CMU), and appeared at the STOC 2013 conference).
