ABSTRACT:
We consider approximation algorithms for the sparsest cut graph partitioning problem. Here, given graphs G with demand pairs {si,ti},
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, we will show 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.
We complement this positive result by showing (a) an integrality gap of a factor of 2 for the Sherali-Adams hierarchy even after
polynomially many rounds, (a) an UG-hardness of 2, and that (c) the problem is as hard as the max-cut problem on general graphs, even
for graphs of treewidth 2.
This is joint work with Kunal Talwar (Microsoft Research SVC) and David Witmer (CMU).
BIO:
Anupam Gupta is an Associate Professor in the Computer Science Department at Carnegie Mellon University, and is visiting
Microsoft Research SVC for Spring 2013. He is interested in the design/analysis of algorithms, specifically in approximation algorithms
for NP-hard optimization problems (with applications to network design, power management, and stochastic optimization), online algorithms,
and the algorithmic study of metric spaces.