YoVDO

Reassembling Trees for the Traveling Salesman

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Combinatorial Optimization Courses Algorithm Design Courses Approximation Algorithms Courses Traveling Salesman Problem Courses Spanning Tree Courses

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

Linear and Discrete Optimization
École Polytechnique Fédérale de Lausanne via Coursera
Linear and Integer Programming
University of Colorado Boulder via Coursera
Approximation Algorithms Part I
École normale supérieure via Coursera
Approximation Algorithms Part II
École normale supérieure via Coursera
Delivery Problem
University of California, San Diego via Coursera