Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Breaching the 2-Approximation Barrier for Connectivity Augmentation

Association for Computing Machinery (ACM) via YouTube

Overview

Explore a groundbreaking conference talk on connectivity augmentation in network design. Delve into the challenge of improving network survivability by adding links to increase connectivity. Learn about the state-of-the-art approaches, including the classification of links and the reduction to the Steiner Tree problem. Discover a novel marking scheme and analysis that breaks the long-standing 2-approximation barrier. Gain insights into the upper bound for cost and the approximation factor analysis. Conclude with a discussion on open problems in this critical area of network optimization and survivability.

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)

Reviews

Start your review of Breaching the 2-Approximation Barrier for Connectivity Augmentation

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.