Data Structures and Algorithms · arXiv:2611.16521 v1 · submitted 12 Nov 2026 · 18 references
Online Survivable Network Design with Arbitrarily Small Connectivity Loss
The paper says
“In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time.”
more of the abstract
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 i̧teGKR12 obtain an O(klog3n)-competitive algorithm, where k is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin i̧teDEHLS18 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.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up. 这篇论文是真正的进步:它表明将连通性损失从2+ε降低到1+ε时仍能获得多对数竞争比,证明完整且包含形式化验证。 This line is wrong
6 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 18 references say.
6 minor objections
The paper says, at Section 1.1, page 2
Pith says: minor objection 1 of 6
In the sentence 'The input is a known loopless undirected multigraph G=(V,E) with n=|V|≥22 vertices and m=|E| edges.', '≥22' appears to be a formatting artifact; it should be '≥2'.
The paper says, at Section 3, page 9, line 'For the parity algorithm, choose...'
Pith says: minor objection 2 of 6
The description of handling zero-cost edges could be clarified: it says 'choose a zero-cost spanning forest inside each zero-cost component, sample a tree after contracting those components for the purpose of tree selection only, and lift the sampled tree using that forest.' A short remark that this preserves the stretch property would be helpful.
show 4 more
The paper says, at Section 4, Lemma 4.1
Pith says: minor objection 3 of 6
The definition of B(a) = 54 ln(1 + 3m/(2a)) uses natural log, while later statements use log with unspecified base. It would be consistent to specify that log here is natural log or that constant factors absorb the base change.
The paper says, at Section 8, running time
Pith says: minor objection 4 of 6
The bound 'O((P+R) MC(n,m) + mR log(m+1) + mn + P n)' uses a generic minimum-cut routine MC(n,m). It would be helpful to cite a specific polynomial-time algorithm (e.g., Stoer–Wagner for global min-cut or Goldberg–Tarjan for s-t min-cut) to confirm polynomiality.
The paper says, at Appendix A, page 23
Pith says: minor objection 5 of 6
The construction using subdivision and average-stretch calls is clearly described. However, the final statement that the uniform distribution over L response trees yields max_e (1/L) sum s_Tt(e) ≤ (32/3) Γ could be accompanied by a brief justification of the constant 32/3 from the multiplicative weights update.
The paper says, at General
Pith says: minor objection 6 of 6
There are a few minor typos: 'polylogarithmic' in the abstract (page 1 line 1) should be 'polylogarithmic'. In the statement of Theorem 1.3, 'E[c(Hi)] ≤ O( log(n+1) log^2(m+1)/ε ) LP(i)' the parentheses around the fraction could be rearranged for clarity.
What would settle it
Independently verify the connectivity-rank bound for the parity-cover algorithm (Lemma 5.2) by simulating a small synthetic example (e.g., n=4, k=3, q=2) and confirming that the number of row procedures does not exceed (q−1)(n−1)=3. This test would validate the core counting argument that each procedure increases the potential Φ_T(K) by at least 1.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic agrees
- Editor wrote the verdict above
- Referee accept: 6 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
关于arXiv:2611.16521的快速看法:这篇论文是一个真正的进步。它解决了在线生存网络设计中一个自然的问题:将连通性损失从已知的2+ε降低到1+ε,同时保持多对数竞争比。证明是完整的,技术(parity shore构造和capped growth)是有创意的,作者还提供了Lean形式化文件——这对结果的可信度是真实加分。
新内容:论文给出了两个算法(parity-cover和direct-cut),覆盖均匀和非均匀要求,竞争比为O(log3 n/ε),当k = Ω(n)时改进到O(log n/ε)。非均匀结果不需要事先知道最大需求,且避免了按需求类别划分。
做得好:证明结构清晰,参数显式设置,引理逐一验证。作者诚实地讨论了局限性,包括精确连通性仍开放,并提供了附录B中的反例来解释为什么独立舍入方法不能直接推广到精确情形。Lean形式化文件表明作者对正确性负有认真态度。
软点:主要理论上的软点是依赖一个未发表的树采样器[3](相同作者)。但附录A给出了基于Abraham-Neiman已发表构造的替代方案,代价只是额外O(log log n)因子。因此主结果仍然成立,只是常数因子略有增加。其他假设(oblivious adversary、单位容量、可行请求)都是该领域的标准,且论文明确陈述了它们。参数选择有些复杂,但似乎正确无误。
总结:对在线网络设计领域的研究者来说,这是一篇有价值的论文。它回答了一个自然的问题,并以令人满意的严格程度进行了证明。我会在我的阅读组中讨论它。
推荐:send to peer review.
The strongest objection
The paper presents a thorough, self-contained analysis with explicit bounds, verified lemmas, and a clear statement of assumptions. The central claim—that a 1+ε connectivity loss yields polylogarithmic competitive ratio—is supported by two distinct algorithmic frameworks, each with a detailed probabilistic and combinatorial justification. The only potential fragility is the reliance on an unpublished spanning-tree sampler (Hajiaghayi [3]) for the headline O(log^3 n) bound, but Appendix A provides an alternative construction from published work (Abraham–Neiman [5]) that incurs only an extra O(log log n) factor. Thus even if the unpublished sampler were invalid, the main result (polylogarithmic competitiveness) survives with a slightly larger exponent. All remaining assumptions (oblivious adversary, unit capacities, feasible requests) are standard and explicitly stated. The proofs of the connectivity-rank bounds (Lemma 5.2, Section 6) and the capped-covering lemma (Lemma 4.1) are logically sound and free of hidden gaps. No load-bearing concern emerges from a careful reading.
The reader's verdict (ACCEPT) is well-reasoned. The paper meets its stated claims with rigorous proofs, acknowledges limitations, and provides alternative constructions for the tree sampler. The only noted assumption (oblivious adversary) is standard in online randomized algorithms and does not compromise correctness. No overlooked contradictions, missing steps, or unverified dependencies were identified in the stress-test. Therefore the verdict should remain unchanged.
The referee's report
If the result holds, it significantly improves the state of the art for online survivable network design by reducing the necessary connectivity loss from a factor of 2+ε to an arbitrarily small factor 1+ε. The competitive ratios are polylogarithmic and independent of the maximum requirement k. The paper also gives a full trade-off (Theorem 1.2) for any target connectivity q ≤ k, showing the role of slack σ = k−q+1. The techniques—especially the capped covering lemma and the connectivity-rank potential—are likely to be applicable to other online covering problems with adaptively chosen rows. The proof is self-contained, with all lemmas proven and parameters explicitly set.
Pith's reading of the paper (a machine's summary, not the authors')
The paper shows that in online survivable network design, where requests require multiple edge-disjoint paths, an algorithm can achieve a polylogcompetitive ratio by providing only a fraction 1/(1+ε) of the required connectivity. This improves on previous work that needed a relaxation factor of at least 2. The result holds for both uniform and nonuniform requirements, with competitive ratios that are polylogarithmic in the network size and independent of the maximum requirement. The algorithms use a novel parity construction and a capped covering framework to control the number of cut repairs.
What carries the argument. The central objects are a parity construction that maps a deficient cut to a set of chords guaranteed to contain many edges from an optimal solution, and a capped multiplicative growth procedure with a deterministic threshold 1/a that prevents coordinates from exceeding 3/(2a). An exponential supermartingale potential Z_S = exp(β a X_S - Y_S) bounds the probability of forced purchases. The analysis also relies on a spanning tree sampler with logarithmic stretch to convert cycle prices to edge costs.
Core claim. The paper proves that for online survivable network design, relaxing the connectivity requirement by a factor of 1+ε (i.e., providing ⌈r/(1+ε)⌉ edge-disjoint paths instead of r) is enough to obtain a polylogarithmic competitive ratio against the optimal offline solution. Two randomized algorithms are given: one using a parity mapping on a spanning tree to reduce the number of distinct cuts, and another using direct cuts for large requirements. For uniform requirements, the competitive ratio is O($ε^{{-1}}$ $log^{3}$ n), which improves to O($ε^{{-1}}$ log n) when the requirement k = Ω(n). For nonuniform requirements, the ratio is O($ε^{{-1}}$ log n $log^{2}$ m). The competitive ratio is independent of k, and both algorithms run in polynomial time.
The premise it rests on. The analysis assumes an oblivious adversary: the request sequence is fixed independently of the algorithm's random choices; if the adversary were adaptive and could see past random outcomes, the probabilistic supermartingale arguments would break.
If the paper is right (Pith's inferences, not the authors')
Online network design can tolerate nearly full connectivity at cost close to the offline optimum, enabling practical fault-tolerant networks where small connectivity loss is acceptable.
The connectivity–cost tradeoff is characterized by the slack σ = k - q + 1, where q is provided connectivity, allowing fine-grained analysis for any target reliability.
The algorithms work on arbitrary multigraphs and run in polynomial time, making them suitable for implementation.
The capped covering lemma may find applications in other online covering problems with many adaptively exposed rows.
The parity construction that compresses the shore family from exponential to O(q log(n/q)) could be used to reduce the constraint set in offline survivable network design.
The direct-cut algorithm avoids tree embeddings entirely, suggesting that tree stretch is not always necessary for good competitive ratios, particularly when requirements are large.
The capped covering technique might yield improved results for online set cover with multiplicity constraints, where each element can be selected only once.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
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. Gupta, Krishnaswamy, and Ravi i̧teGKR12 obtain an O(klog3n)-competitive algorithm, where k is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin i̧teDEHLS18 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.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 1.00
“We show that relaxing the connectivity requirement by a factor of only $1+\varepsilon$ suffices to obtain a polylogarithmic competitive ratio.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.11 · states limitation 0.44 · human participants 0.02 · controlled comparison 0.16 · randomized assignment 0.01 · states quantitative result 0.95 · compares with prior results 0.97 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. | background 1.00 | 0.06 | 0.01 | asserted 0.99 |
| 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. | background 1.00 | 0.07 | 0.02 | asserted 0.99 |
| The goal is to keep the total cost close to that of an optimal offline solution. | background 1.00 | 0.07 | 0.04 | asserted 0.97 |
| 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. | background 1.00 | 0.02 | 0.03 | asserted 1.00 |
| 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$. | background 0.99 | 0.03 | 0.03 | asserted 1.00 |
| We show that relaxing the connectivity requirement by a factor of only $1+\varepsilon$ suffices to obtain a polylogarithmic competitive ratio. | result 0.55 | 0.96 | 0.96 | asserted 1.00 |
What kind of paper the classifier reports this is: theoretical result 0.94 · evidence from proof or derivation 0.88
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 5,090 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (3)
Figures are the authors', reproduced from the paper.
References (18)
- [3] Mohammad Hajiaghayi. Logarithmic embeddings into probabilistic spanning trees for dis- tances and capacities, 2026. URLhttps://arxiv.org/abs/2611.05189. arXiv:2611.05189 on PithPith's reviewarXiv
- [1] Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and stochastic surviv- able network design.SIAM Journal on Computing, 41(6):1649–1672, 2012. doi: 10.1137/ 09076725X. URLhttps://www.contrib.andrew.cmu.edu/ ~ravi/sicomp12.pdf. Prelimi- nary version in STOC 2009 on Pith
- [2] Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Sed- dighin. Greedy algorithms for online survivable network design. In45th International Collo- quium on Automata, Languages, and Programming (ICALP), volume 107 ofLeibniz Interna- tional Proceed... on Pithdoi:10.4230/lipics.icalp.2018.152
- [4] Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to thek-server problem.SIAM Journal on Computing, 24(1):78–100, 1995. doi: 10.1137/S0097539792224474. URLhttps://dwest.web.illinois.edu/pubs/kserver.pdf on Pithdoi:10.1137/s0097539792224474
- [5] Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch span- ning tree.SIAM Journal on Computing, 48(2):227–248, 2019. doi: 10.1137/17M1115575. Preliminary version in STOC 2012 on Pithdoi:10.1137/17m1115575
- [6] Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem.SIAM Journal on Discrete Mathematics, 4(3):369–384, 1991. doi: 10.1137/0404033 on Pithdoi:10.1137/0404033
- [7] Piotr Berman and Chris Coulston. On-line algorithms for Steiner tree problems (extended ab- stract). InProceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pages 344–353. ACM, 1997. doi: 10.1145/258533.258618 on Pithdoi:10.1145/258533.258618
- [8] Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. doi: 10.1007/s004930170004 on Pithdoi:10.1007/s004930170004
- [9] Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson. Tight bounds for online weighted tree augmentation. In46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 ofLeibniz International Proceedings in Informatics, pages 88:1–88:... on Pithdoi:10.4230/lipics
- [10] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem.SIAM Journal on Computing, 39(2):361–370, 2009. doi: 10.1137/060661946. Preliminary version in STOC 2003 on Pithdoi:10.1137/060661946
- [11] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009. doi: 10.1287/moor.1080.0363. 21 on Pithdoi:10.1287/moor.1080.0363
- [12] Sander Borst, Marek Eli´ aˇ s, and Moritz Venzin. Stronger adversaries grow cheaper forests: Online node-weighted Steiner problems. InProceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 3842–3864. SIAM, 2025. doi: 10.1137/1.9781611978322 on Pithdoi:10.1137/1.9781611978322
- [13] Mohit Garg and Aditya Subramanian. Online connectivity augmentation. InProceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 85–104. SIAM, on Pith
- [14] Mohit Garg, Felix Hommelsheim, and Alexander Lindermayr. Optimal online weighted con- nectivity augmentation, 2026. URLhttps://arxiv.org/abs/2610.42046. arXiv:2610.42046 on PithPith's reviewarXiv
- [15] Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, and Michael Zlatin. Weighted and unweighted online connectivity augmentation via geometric hitting set, 2026. URLhttps: //arxiv.org/abs/2611.08570. arXiv:2611.08570 on PithPith's reviewarXiv
- [16] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbi- trary metrics by tree metrics.Journal of Computer and System Sciences, 69(3):485–497, 2004. doi: 10.1016/j.jcss.2004.04.011. Preliminary version in STOC 2003. A Constructing a spanning-tr... on Pithdoi:10.1016/j.jcss.2004.04.011
- [129] URLhttps://arxiv.org/abs/2410.18542 on PithPith's reviewarXiv
- [2026] doi: 10.1137/1.9781611978971.4 on Pithdoi:10.1137/1.9781611978971.4
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment