Completed
The Cut-LP
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
On LP-Relaxations for the Tree Augmentation Problem
Automatically move to the next video in the Classroom when playback concludes
- 1 The Tree Augmentation Problem
- 2 Equivalent Formulation 2
- 3 Why is it interesting?
- 4 The Cut-LP
- 5 Dual-fitting algorithms
- 6 Shadow-minimal solutions
- 7 Properties of shadow minimal solutions
- 8 Twin-links and stems
- 9 Blocking trees
- 10 An LP and its dual
- 11 Initial assignment of duals
- 12 The algorithm
- 13 Additional possible constraints
