Главная
Study mode:
on
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
Description:
Explore a groundbreaking lecture on the Connectivity Augmentation Problem (CAP) presented by Afrouz Jabal Ameli at the Hausdorff Center for Mathematics. Delve into the state-of-the-art research that breaches the long-standing 2-approximation barrier for CAP. Learn about the classification of links, incident links, and the innovative reduction to the Steiner Tree problem. Discover the lower bound techniques, approximation algorithms, and the novel marking scheme that led to this significant advancement. Examine the analysis of the approximation factor, grouping strategies, and recent advances in the field. Conclude with a discussion on open problems, providing insights into future research directions in graph connectivity augmentation.

Breaching the 2-Approximation Barrier for Connectivity Augmentation

Hausdorff Center for Mathematics
Add to list