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

Delivery Problem
University of California, San Diego via Coursera
Dynamic Programming
YouTube
What Is the Best Way to Lace Your Shoes? Dream Proof
Mathologer via YouTube
The Traveling Salesman Problem - When Good Enough Beats Perfect
Reducible via YouTube
Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A
Association for Computing Machinery (ACM) via YouTube