Ola Svensson: Polyhedral Techniques in Combinatorial Optimization: Matchings and Tours

We overview recent progress on two of the most classic problems in combinatorial optimization: the matching problem and the traveling salesman problem. We focus on deterministic parallel algorithms for the perfect matching problem and the first constant-factor approximation algorithm for the asymmetric traveling salesman problem. While these questions pose seemingly different challenges, recent progress has been achieved using similar polyhedral techniques. In particular, for both problems, we will explain the use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of better algorithms.