Online Connectivity Augmentation
For researchers in fault-tolerant network design and online algorithms, this work provides the optimal competitive ratio for a fundamental problem, resolving its online complexity.
This paper studies the Connectivity Augmentation Problem (CAP) in an online setting, where requests arrive sequentially and must be served by adding links to a k-edge-connected graph to achieve (k+1)-edge-connectivity. The authors obtain a tight competitive ratio for online CAP, improving upon previous bounds.
The Connectivity Augmentation Problem (CAP) is a fundamental problem in fault-tolerant network design and has been extensively studied in the context of approximation algorithms. In this work, we consider CAP in the online setting: given a $k$-edge-connected graph $G$ and a set $L$ of additional edges over the vertices of $G$, called links, online requests arrive one by one, each specifying two vertices that need to be $(k+1)$-edge-connected. We start with the graph $G$ and progressively add links to serve these requests. More specifically, upon the arrival of a request $\{u,v\}$, we must immediately and irrevocably add zero or more links from $L$ to the graph so that $u$ and $v$ are $(k+1)$-edge-connected in the resulting augmented graph. The goal is to minimize the total number of links added, and we evaluate an algorithm's performance by its competitive ratio relative to an optimal offline solution. In this work, improving upon previous bounds, we obtain a tight competitive ratio for online CAP, along with other related results.