Approximation Algorithm for Survivable Network Design

Decanato - Facoltà di scienze informatiche

Data: 19 Aprile 2021 / 13:00 - 14:30

Online

You are cordially invited to attend the PhD Dissertation Defence of Afrouz Jabalameli on Monday 19 April 2021 at 13:00 on Zoom.

Abstract:
Many relevant discrete optimization problems are believed to be hard to solveefficiently (i.e. they cannot be solved in polynomial time unless P=NP). Anapproximation algorithm is one of the ways to tackle these hard optimizationproblems. These algorithms have polynomial running time and compute a feasiblesolution whose value is within a proven factor approximation factor of theoptimal solution value. The field of approximation algorithms has grown quicklyover the last few decades, leading to the development of several algorithmicand analytical techniques. In this doctoral dissertation, we focus onSurvivable Network Design problems, where the goal is to construct low-costnetworks that are resilient to a few edge/node faults. More specifically, weconsider a basic problem in this area, which is the Connectivity Augmentationproblem (CAP). In this problem, we are given a $k$-edge-connected graph(namely, a graph in which removing any $k-1$ edges preserves the connectivityof the graph) and a collection of extra edges links. Our goal is to identify aminimum cardinality subset of links whose addition to the graph makes it$(k+1)$-edge connected. This problem is NP-hard and has many interestingreal-world applications; For this reason, it has been studied through the lensof approximation algorithms in the past. Despite the efforts of severalresearchers, no progress was made on this problem after the $2$-approximationalgorithm by Frederikson et al. [1981]. We remark that a $2$ approximation is knowneven for wide generalizations of CAP. The main contribution of this thesis isbreaching the $2$ approximation barrier for CAP by presenting a $1.91$approximation algorithm. Our result is based on a non-trivial reduction toanother fundamental problem, Steiner Tree. Along the way to this mainachievement, we studied a special case of CAP, the Cycle Augmentation problem(CycAP) for which $2$ was the best-known approximation factor. Here we aregiven a cycle plus additional links, and the goal is to find a subset of linkswith minimum size whose addition to $G$ makes it $3$-edge-connected. We showthat CycAP is APX-hard, in particular, it does not admit an approximationfactor arbitrarily close to $1$ (even the NP-hardness of this problem was notknown earlier). Furthermore, we present a $3/2+\epsilon$ approximationalgorithm for any constant $\epsilon>0$.

Dissertation Committee:
- Prof. Fabrizio Grandoni, IDSIA USI-SUPSI, Switzerland (Research Advisor)
- Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland(Internal Member)
- Prof. Stefan Wolf, Università della Svizzera italiana, Switzerland (InternalMember)
- Prof. Jaroslaw Byrka, University of Wroclaw, Poland (External Member)
- Prof. Stefano Leonardi, Sapienza University of Rome, Italy (External Member)