Completed
The algorithm by Cosmadakis & Papadimitriou, SICOMP 1984
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Single-machine scheduling with few job classes
- 3 A TSP formulation
- 4 Applications
- 5 Previous work
- 6 The algorithm by Cosmadakis & Papadimitriou, SICOMP 1984
- 7 Example
- 8 A first simple algorithm
- 9 Solution
- 10 Formulating the improved algorithm
- 11 The improved algorithm / 2
- 12 Complexity analysis
- 13 Final run time improvements / 1
- 14 Summary
