On the Cycle Augmentation Problem: Hardness and Approximation Algorithms.

Abstract: In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum cardinality whose addition to the graph makes it (k+1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k=1 (a.k.a. the Tree Augmentation Problem or TAP) or k=2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2
approximation algorithms are known for TAP, nothing better is known for CacAP (hence for k-Connectivity Augmentation in general).

As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, which we call the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard.

In this talk we present a combinatorial (3/2+eps)-approximation for CycAP. We also present an LP formulation with a matching integrality gap, which might be useful to address the general case of the problem.

This is joint work with Fabrizio Grandoni, Afrouz Jabal Ameli and Krzysztof Sornat.

Date: Nov 13, 2019 at 14:30:00 h
Venue: Sala 33, Av. República 701.
Speaker: Waldo Galvez
Affiliation: IDSIA.
Coordinator: Prof. José Verschae
More info at:
Event website

Posted on Nov 12, 2019 in ACGO, Seminars