NeFut Logo NeFut
中 Admin Login

[CS.DS] Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting Set

Published at: 2026-11-09 22:00 Last updated: 2026-11-12 00:51
#algorithm #optimization #Graph

We study the Online Connectivity Augmentation Problem (OCAP). Given a $k$‑edge‑connected graph $G=(V,E)$ with $|V|=n$ and a candidate link set $L\subseteq \binom{V}{2}$, each round a minimum cut $C$ arrives and we must maintain a smallest set of links crossing all such cuts, i.e., a minimum hitting set for $\{\delta_L(C):|\delta_E(C)|=k\}$. This is an online hitting‑set instance where the ground set is $L$ and the arriving sets belong to $\mathcal{C}=\{\delta_L(C):|\delta_E(C)|=k\}$. Using the classic online set‑cover algorithm of Alon et al., a $O(\log^2 n)$‑competitive algorithm follows. When $k$ is odd, OCAP reduces to a tree case; Naor, Umboh and Williamson gave an optimal $O(\log n)$‑competitive algorithm that also works for weighted instances. More recently, Garg and Subramanian achieved $O(\log n)$ competitiveness for unweighted OCAP in the node‑arrival model, but this does not cover cut arrivals. No better than $O(\log^2 n)$ was known for weighted OCAP under cut arrivals. Our contributions are twofold: (1) a $O(\log n\log\log n)$‑competitive algorithm for weighted OCAP with cut arrivals, nearly matching the lower bound; (2) an optimal $O(\log n)$‑competitive algorithm for unweighted OCAP with cut arrivals. We also present an $O(1)$ algorithm for Online Cycle Augmentation under node arrivals. Since a cycle under cut arrivals admits no $o(\log n)$‑competitive algorithm, this establishes a separation between the best achievable ratios in the two arrival models.\n\nReview: By framing OCAP as a geometric hitting‑set problem, the paper pushes the competitive ratio for weighted instances from $O(\log^2 n)$ to almost optimal $O(\log n\log\log n)$ and clarifies the intrinsic gap between node‑ and cut‑arrival models, offering valuable directions for future online network augmentation research.

Original Source: https://arxiv.org/abs/2611.08570

[h] Back to Home