Breaching the 2-Approximation Barrier for Connectivity Augmentation
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Introduction: Survivable Network Design
Connectivity Augmentation Problem
State of the art
Classification of Links
Cross
Reduction to Steiner Tree
Reduction to the Steiner Tree Problem
Reduction from CAP to Steiner Tree
Lower Bound
Obtaining Approximation Algorithm
Steiner Tree Algorithm
Our Marking Scheme
Upper Bound for c
Analysis of the Approximation Factor
Grouping
Open Problems
Taught by
Association for Computing Machinery (ACM)