Completed
Obtaining Approximation Algorithm
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Breaching the 2-Approximation Barrier for Connectivity Augmentation
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Connectivity Augmentation Problem (CAP)
- 3 State of the art (Prior to our work)
- 4 Our Results
- 5 Classification of Links
- 6 Incident Links
- 7 Reduction to Steiner Tree
- 8 Reduction to the Steiner Tree Problem
- 9 Reduction from CAP to Steiner Tree
- 10 Lower Bound
- 11 Obtaining Approximation Algorithm
- 12 Steiner Tree Algorithm
- 13 How to improve?
- 14 Our Marking Scheme
- 15 Upper Bound for
- 16 Analysis of the Approximation Factor
- 17 Grouping
- 18 Recent Advances
- 19 Open Problems
