Reassembling Trees for the Traveling Salesman
Offered By: Hausdorff Center for Mathematics via YouTube
Course Description
Overview
Explore a lecture on advanced approximation algorithms for the traveling salesman problem and its variants. Delve into the technique of exploiting spanning tree convex combinations from linear programming relaxations. Learn how randomly sampling trees from these distributions can yield better approximation guarantees than traditional minimum cost spanning tree methods. Discover a novel approach involving tree reassembly before sampling, which can enhance solution properties. Examine the application of this method to the metric s-t-path TSP, resulting in a deterministic polynomial-time algorithm that improves upon previous approximation ratios. Cover topics including problem description, algorithm analysis, narrow cuts, and spanning trees in this comprehensive exploration of cutting-edge combinatorial optimization techniques.
Syllabus
Introduction
Problem description
Algorithm description
Basic analysis
Improvements
Narrow cuts
Spanning trees
Remarks
Taught by
Hausdorff Center for Mathematics
Related Courses
Delivery ProblemUniversity of California, San Diego via Coursera Dynamic Programming
YouTube What Is the Best Way to Lace Your Shoes? Dream Proof
Mathologer via YouTube The Traveling Salesman Problem - When Good Enough Beats Perfect
Reducible via YouTube Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A
Association for Computing Machinery (ACM) via YouTube