Oct. 30, 3:30pm, Gates 8115 (Note unusual location)

Thomas Rothvoß, University of Washington

The matching polytope has exponential extension complexity

Thomas Rothvoß, University of Washington

The matching polytope has exponential extension complexity

Abstract:

A popular method in combinatorial optimization is to express polytopes
*P*, which may potentially have exponentially many facets, as
solutions of linear programs that use few extra variables to reduce the
number of constraints down to a polynomial. After two decades of
standstill, recent years have brought amazing progress in showing lower
bounds for the so called extension complexity, which for a polytope *P*
denotes the smallest number of inequalities necessary to describe a
higher dimensional polytope *Q* that can be linearly projected on *P*.
However, the central question in this field remained wide open: can the
perfect matching polytope be written as an LP with polynomially many
constraints? We answer this question negatively. In fact, the extension
complexity of the perfect matching polytope in a complete n-node graph
is *2*^{Ω(n)}.