Polyhedral Techniques in Combinatorial Optimization - Matchings and Tours

Explore recent advancements in combinatorial optimization through this 39-minute lecture focusing on the matching problem and the traveling salesman problem. Delve into deterministic parallel algorithms for perfect matching and the groundbreaking constant-factor approximation algorithm for the asymmetric traveling salesman problem. Discover how similar polyhedral techniques have led to progress in these seemingly disparate challenges. Examine the use of linear programming formulations, including exponential-sized ones, to extract structural information from problem instances and guide the development of improved algorithms. Gain insights into cutting-edge research in the field of combinatorial optimization presented by Ola Svensson at the Hausdorff Center for Mathematics.

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