Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Hausdorff Center for Mathematics via YouTube

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

Reviews

Start your review of Beating the Integrality Ratio for S-T-Tours in Graphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.