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.

Go to recording (lecture starts at 3:30)