## Speaker:

## Affiliation:

Carnegie Mellon University

Department of Computer Science

7203 Gates Building

Pittsburg, PA 15213

United States of America

## Webpage:

## Time:

## Venue:

- AG-69

## Organisers:

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).