YoVDO

Beating the Integrality Ratio for S-T-Tours in Graphs

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Traveling Salesman Problem Courses Combinatorial Optimization Courses Polynomial Time Algorithm Courses

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 Computing
Hausdorff 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