Completed
Overview: sequence of reductions
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
An Improved Approximation Algorithm for ATSP
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 The asymmetric traveling salesman problem
- 3 History of approximation ratios for ATSP
- 4 Linear Programming Relaxation
- 5 Overview: sequence of reductions
- 6 Strongly laminar instances
- 7 Naive recursive algorithm
- 8 Analysis: nice paths
- 9 Recursion with vertebrate pairs
- 10 Constructing the backbone
- 11 Summary: State of the Art for ATSP
