event
ARC Colloquium: Gábor Braun
Primary tabs
Title: Limiting linear programs through common information
Abstract:
Efficiently optimizing linear functions over a polytope by directly solving the linear program requires a compact representation of the polytope, e.g., as an affine image of a polytope with few facets. We present an information theoretic approach for proving limits of such extension: the common information shared by the vertices and facets.
This framework not only improves recent lower bounds on the CLIQUE polytope by Braverman and Moitra, but also provides a much simplified proof, and is stable under perturbations of the polytope.
This is an ongoing joint work with Sebastian Pokutta.
Groups
Status
- Workflow status: Published
- Created by: Elizabeth Ndongi
- Created: 02/27/2013
- Modified By: Fletcher Moore
- Modified: 10/07/2016
Categories
Keywords
- No keywords were submitted.