Wednesday 22 October 2014
3pm - 4.30pm, 32L.G.20, LSE
Abstract
We consider several problems where the goal is partition a ground set into several pieces while minimizing a "cut-type" objective function; examples include Multiway Cut, Node-weighted Multiway Cut, Metric Labeling and Hypergraph Labeling. A natural LP relaxation gives an optimal approximation for these problems, assuming the Unique Games Conjecture (the UGC assumption can be removed for certain submodular generalizations of these problems). However, we do not know how to round this LP in general and the focus has been on understanding this LP for specific problems. In this talk, we describe several rounding strategies and an integrality gap construction that leads to a simplex coloring conjecture reminiscent of Sperner’s Lemma.
This talk is based on joint work with Chandra Chekuri (UIUC), Huy Nguyen (Simons Institute Berkeley), Jan Vondrak (IBM Research Almaden), and Yi Wu (Google).