Ola Svensson (EPFL):
Polyhedral Techniques in Combinatorial Optimization
Abstract:
In this talk, we will survey recent use of polyhedral techniques in combinatorial optimization. In particular, we introduce techniques for using linear programming formulations, even exponential-sized ones, to extract structure from problem instances that guides the design of algorithms.
The talk will focus on two results: a constant-factor approximation algorithm for the asymmetric traveling salesman problem and a deterministic parallel algorithm for the perfect matching problem. The so-called laminar structure of the considered linear programming formulations plays a central role in both these results.
Finally, we discuss several intriguing research directions and open questions related to these problems.