Polyhedral Techniques in Combinatorial Optimization: Matchings and Tours

Explore recent advancements in combinatorial optimization through this 42-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. Access accompanying slides for a comprehensive understanding of polyhedral techniques in combinatorial optimization, with emphasis on matchings and tours.