The Matching Polytope has Exponential Extension Complexity
The Matching Polytope has Exponential Extension Complexity
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 …