Beating the Integrality Ratio for S-T-Tours in Graphs
Offered By: Hausdorff Center for Mathematics via YouTube
Course Description
Overview
Explore a groundbreaking lecture on the s-t-path graph Traveling Salesman Problem (TSP) that surpasses the known integrality ratio of 3/2. Delve into a polynomial-time algorithm with an improved approximation ratio of 1.497, presented as part of the Combinatorial Optimization workshop at the Hausdorff Center for Mathematics. Discover novel techniques introduced by the speaker, including a new type of ear-decomposition, an enhanced ear induction linked to matroid union, a stronger lower bound, and a method to reduce general instances to those where s and t have small distances. Gain insights into this collaborative work that refines previous approximation algorithms and pushes the boundaries of combinatorial optimization in graph theory.
Syllabus
Vera Traub: Beating the integrality ratio for s-t-tours in graphs
Taught by
Hausdorff Center for Mathematics
Related Courses
A Market for Scheduling, with Applications to Cloud ComputingHausdorff Center for Mathematics via YouTube A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Simons Institute via YouTube An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor
Simons Institute via YouTube Optimization: Interior Point Methods - Part 2
Simons Institute via YouTube Optimization: Interior Point Methods - Part 1
Simons Institute via YouTube