{"arxiv_id":"2611.16521","title":"Online Survivable Network Design with Arbitrarily Small Connectivity Loss","abstract":"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.\n  Gupta, Krishnaswamy, and Ravi~\\cite{GKR12} obtain an $O(k\\log^3 n)$-competitive algorithm, where $k$ is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~\\cite{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of $2+\\varepsilon$. We show that relaxing the connectivity requirement by a factor of only $1+\\varepsilon$ suffices to obtain a polylogarithmic competitive ratio.","primary_cat":"cs.DS","cross_cats":[],"submitted_at":"2026-11-12T09:17:32+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"ACCEPT","confidence":"HIGH","one_line_summary":"Relaxing the connectivity requirement by a factor of 1+ε yields a polylogarithmic competitive ratio for online survivable network design, improving on previous bicriteria results requiring a factor of 2+ε.","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.16521","verdict":"/api/v1/verdicts/2611.16521"}}