Back
Texte intégral
Doctoral thesis

Approximation algorithms for survivable network design

    19.04.2021

74 p

Thèse de doctorat: Università della Svizzera italiana, 2021

Approximation algorithms
Network design
Connectivity augmentation problem
Cactus augmentation problem
Survivable network design
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 low-cost 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 k-edge-connected 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 NP-hard 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 2-approximation 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 non-trivial 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 best-known 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 3-edge-connected. We show that CycAP is APX-hard, in particular it does not admit an approximation factor arbitrarily close to 1 (even the NP-hardness of this problem was not known earlier). Furthermore, we present a 3/2+ε approximation algorithm for any constant ε > 0.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1319194
Statistics
Document views: 158 File downloads:
  • 2021INFO005.pdf: 176