YoVDO

A 1.5-Approximation for Path TSP

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Travelling Salesman Problem (TSP) Courses Algorithm Design Courses Dynamic programming Courses Combinatorial Optimization Courses Approximation Algorithms Courses

Course Description

Overview

Explore a groundbreaking lecture on the Metric Path Traveling Salesman Problem (path TSP), presenting a 1.5-approximation algorithm. Delve into the innovative approach that deviates from previous techniques by focusing on larger s-t cuts rather than solely on narrow cuts. Discover how a variation of dynamic programming, combined with Karger's seminal result on near-minimum cuts, leads to a well-structured point in the Held-Karp relaxation. Learn about this simpler algorithm that matches Christofides' unbeaten 1.5-approximation guarantee for TSP without introducing additional error terms. Gain insights into how this advancement could potentially lead to improvements in TSP approximation algorithms.

Syllabus

Rico Zenklusen: A 1.5-approximation for path TSP


Taught by

Hausdorff Center for Mathematics

Related Courses

The Traveling Salesman Problem - When Good Enough Beats Perfect
Reducible via YouTube
A Slightly Improved Approximation Algorithm for Metric TSP
Simons Institute via YouTube
Reducing Path TSP to TSP
Association for Computing Machinery (ACM) via YouTube
The Transformer Network for the Traveling Salesman Problem
Institute for Pure & Applied Mathematics (IPAM) via YouTube
Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP
Hausdorff Center for Mathematics via YouTube