A Personal History (With Karp Reductions!)

on YouTube ↗19m

" summary

Chronological takeaways: the Held-Karp subtour LP remains the fundamental relaxation for TSP and modern solvers like Concord now solve instances up to ~25,000 cities; a constructive algorithm for cubic bipartite graphs returns a TSP tour of size at most 9n/7 - 2 by finding a cycle cover with few cycles and stitching a spanning tree; the online bipartite ranking method gives the classic constant-factor guarantee for adversarial arrivals, while a greedy reduction yields a 1/2-competitive policy for omni-channel order allocation and a matching hardness rules out improvement unless NP = RP.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:28Enjoying a nice day
3. 1:44Learning UNIX
4. 2:38Fast Forward
5. 3:09Linear Programming Relaxation
6. 4:21Concord Solver
7. 4:49Traveling Salesman
8. 5:42Barnetts Conjecture
9. 5:56polynomial time algorithm
10. 6:08general approach
11. 7:03omnichannel retailing
12. 8:23optimization problems
13. 9:00Karpov
14. 9:16Graph
15. 11:14Online Problem
16. 17:46Conclusion