Online Vertex Connectivity Augmentation
Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
原文摘要
Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).
cs.DS