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
Approximation Algorithms Part IÉcole normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX Delivery Problem
University of California, San Diego via Coursera