Approximation algorithms for survivable network design
74 p
Thèse de doctorat: Università della Svizzera italiana, 2021
English
Many relevant discrete optimization problems are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and compute a feasible solution whose value is within a proven factor (approximation factor) of the optimal solution value. The field of approximation algorithms has grown quickly over the last few decades, leading to the development of several algorithmic and analytical techniques. In this doctoral dissertation, we focus on Survivable Network Design problems, where the goal is to construct lowcost networks that are resilient to a few edge/node faults. More specifically, we consider a basic problem in this area, that is the Connectivity Augmentation problem (CAP). In this problem, we are given a kedgeconnected graph (namely, a graph in which removing any k 1 edges preserves the connectivity of the graph) and a collection of extra edges (links). Our goal is to identify a minimum cardinality subset of links whose addition to the graph makes it (k+1)edge connected. This problem is NPhard and has many interesting real world applications; For this reason it has been studied through the lens of approximation algorithms in the past. Despite the efforts of several researchers, no progress was made on this problem after the 2approximation algorithm by Frederickson and JáJá [1981]. We remark that a 2 approximation is known even for wide generalizations of CAP. The main contribution of this thesis is breaching the 2 approximation barrier for CAP by presenting a 1.91 approximation algorithm. Our result is based on a nontrivial reduction to another fundamental problem, Steiner Tree. Along the way to this main achievement, we studied a special case of CAP, the Cycle Augmentation problem (CycAP) for which 2 was the bestknown approximation factor. Here we are given a cycle plus additional links, and the goal is to find a subset of links with minimum size whose addition to G makes it 3edgeconnected. We show that CycAP is APXhard, in particular it does not admit an approximation factor arbitrarily close to 1 (even the NPhardness of this problem was not known earlier). Furthermore, we present a 3/2+ε approximation algorithm for any constant ε > 0.

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://susi.usi.ch/usi/documents/319194