Online Connectivity Augmentation

The Connectivity Augmentation Problem (CAP) is a fundamental problem in faulttolerant 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 with n vertices 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.

Prior works by Gupta, Krishnaswamy, and Ravi (2009) and Naor, Umboh, and Williamson (2019) imply the following bounds on the competitive ratio for online CAP: a randomized Õ(k log 3 n) upper bound, a deterministic O(log n) upper bound for the special case k = 1 (also known as the online Tree Augmentation Problem (TAP)), and an Ω(log n) lower bound. These bounds also extend to the weighted setting, where links have weights and the objective is to minimize the total weight of the links added. We show the following.