Improved Approximation Algorithms for the TSP and S-t-path TSP

on YouTube ↗01h 01m

" summary

Survey of concrete advances: metric TSP stays at 3/2 for tours while the S–T path gap drops from Hoogeveen’s 5/3 using a concrete algorithmic recipe: solve the Held‑Karp LP, decompose into spanning trees, sample a tree (best-of-many Christofides), and bound expected T‑join cost via laminar Gao trees and narrow‑cut structure. Iterated recursive dynamic programming then yields algorithms with ratio 3/2+ε (provable) and several intermediate analyses give 1.6 and 1.566 guarantees.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 1:19The Metric Case
3. 3:09The Thin Tree Approach
4. 8:25How Does Randomization Help
5. 9:38Christa PDS
6. 13:45Notation
7. 14:25Polyhedral Combinatorics
8. 16:53Standard LP Relaxation
9. 18:30Fractional Tjoint
10. 20:59Integrality Gap
11. 21:49LP
12. 23:46Best of many Christinas
13. 24:50Randomized version
14. 27:34Thirds bound
15. 30:03Lemma
16. 48:45Fractional TSP
17. 49:48General Metrics
18. 53:01Progress