Speaker: |
Anupam Gupta (Carnegie Mellon University Department of Computer Science 7203 Gates Building Pittsburg, PA 15213 United States of America) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Wednesday, 5 Mar 2014, 16:00 to 17:00 |

Venue: |
AG-69 |

(Scan to add to calendar)

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