Polyhedral techniques in combinatorial optimization: matchings and tours

Abstract

We overview recent progress on two of the most classical problems in combinatorial optimization, namely 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 use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of algorithms.