Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Reassembling Trees for the Traveling Salesman

Hausdorff Center for Mathematics via YouTube

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

Reviews

Start your review of Reassembling Trees for the Traveling Salesman

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.