Discrete Lunch‎ > ‎

2nd Lunch: Lower bounds on sizes of extended formulations

posted Aug 8, 2013, 7:48 AM by Dirk Oliver Theis   [ updated Aug 8, 2013, 7:53 AM ]
Mon June 10.
Our visitor Kanstantsin Pashkovich gave a talk on how to lower-bound sizes of extended formulations.  Given a combinatorial optimization problem (matching, spanning tree, max-cut, traveling salesman problem, ...) one wants to find lower bounds on how many inequalities a Linear Program must have in order to model the problem.
The name "extended formulation" comes from the combinatorial optimization practice to start with a Linear Programming formulation, and then try to add a bunch of new variables together with (few) inequalities, so that the original inequalities become redundant.
Kostya explained the connection to Communication Complexity.