Online Survivable Network Design with Arbitrarily Small Connectivity Loss

In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. Each request is a pair of vertices $(s,t)$ with a connectivity requirement k, and the algorithm must irrevocably buy edges so that s and t are joined by k edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~{GKR12} obtain an O(klog³ n)-competitive algorithm, where k is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of 2+ε. We show that relaxing the connectivity requirement by a factor of only 1+ε suffices to obtain a polylogarithmic competitive ratio.