Completed
Concentration property
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
A Slightly Improved Approximation Algorithm for Metric TSP
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Metric TSP
- 3 Christofides' Algorithm
- 4 Approximation algorithms
- 5 Background #2: 2-uniform spanning trees
- 6 Algorithm we study
- 7 Why 2-uniform trees may help
- 8 Concentration property
- 9 A feasible solution
- 10 Applying a small perturbation
- 11 Cuts of interest
- 12 Stars have no even near min cuts
- 13 Degree cut case
- 14 Dream of induction
- 15 Example hierarchy
- 16 Increasing slack
- 17 Overall approach
- 18 Using probabilistic tool #1
- 19 Using probabilistic tool #2
- 20 Analysis
- 21 Next steps for polynomial geometers
