event
ARC Colloquium: Sebastian Pokutta, Georgia Tech
Primary tabs
Title: Extended formulations and complexity of polytopes
Abstract:
In the first part we will analyze extended formulations of polytopes and we solve a 20-year old problem posed by Yannakakis: there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope.
In view of the aforementioned lower bounds we then turn our attention, in the second part, to approximate extended formulations which approximately project to the desired polytope. We develop a framework for proving approximation limits of polynomial-size linear programs. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2−ε})-approximations for CLIQUE require linear programs of size 2^{n^Ω(ε)}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs.
This is joint work with G ́abor Braun, Samuel Fiorini, Serge Massar, David Steurer, Hans Raj Tiwary, and Ronald de Wolf
Groups
Status
- Workflow Status:Published
- Created By:Elizabeth Ndongi
- Created:11/05/2012
- Modified By:Fletcher Moore
- Modified:10/07/2016
Categories
Keywords