betaFeedback

WorksComputer Science

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)(s,t) with a connectivity requirement kk, and the algorithm must irrevocably buy edges so that ss and tt are joined by kk edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~\cite{GKR12} obtain an O(klog⁡3n)O(k\log^3 n)-competitive algorithm, where kk 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+ε2+\varepsilon. We show that relaxing the connectivity requirement by a factor of only 1+ε1+\varepsilon suffices to obtain a polylogarithmic competitive ratio.

Introduction

In online survivable network design, the network is known in advance but the pairs that need protection against edge failures arrive over time. On the arrival of a request, consisting of a pair (s,t)(s,t) and a requirement kk, an algorithm must buy enough edges to provide kk edge-disjoint ss–tt paths. Bought edges remain available, and their cost is paid only once. The objective is to compete with the least expensive network that serves all requests seen so far. Unlike ordinary online connectivity, this problem must preserve several independent routes while making irrevocable decisions about which routes to share. When requirements differ between requests, kk denotes the largest one.

Gupta, Krishnaswamy, and Ravi [1] gave a randomized O(klog⁡3n)O(k\log^{3}n)-competitive algorithm that provides the full requirement kk. Their method uses spanning trees and an online covering problem whose explicit representation has size mO(k)m^{O(k)}. A different direction is to relax the amount of connectivity. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin [2] obtained polylogarithmic bicriteria guarantees by providing only k/2k/2 edge-disjoint paths when all requirements equal kk. In the rooted case, their competitive ratio is O(log⁡n)O(\log n); for arbitrary pairs it is O(log⁡2n)O(\log^{2}n).

These results leave a natural question: is a loss of half the connectivity necessary to obtain a competitive ratio independent of kk? We show that it is not: every prescribed relative slack is sufficient. Fix any 0<ε≤10<\varepsilon\leq1. For a request with requirement kk, our algorithm always provides ⌈k/(1+ε)⌉\lceil k/(1+\varepsilon)\rceil edge-disjoint paths. Its expected cost is compared with the cheapest network that provides all kk paths, and its competitive ratio is polylogarithmic times 1/ε1/\varepsilon. When all requirements equal kk, the competitive ratio is O(log⁡3n/ε)O(\log^{3}n/\varepsilon), and if moreover kk is at least a constant fraction of nn, the competitive ratio drops to O(log⁡n/ε)O(\log n/\varepsilon). When requirements differ, every request still receives a 1/(1+ε)1/(1+\varepsilon) fraction of its own requirement, rounded up, and the competitive ratio is O(log⁡nlog⁡2m/ε)O(\log n\log^{2}m/\varepsilon).

This competitive ratio does not grow with the largest requirement, and the algorithm does not need to know that requirement in advance. The algorithm runs in polynomial time in terms of the input size, regardless of the value of kk. It is randomized, never fails to provide the promised connectivity, and its cost guarantee holds in expectation at every point of a request sequence that is fixed in advance. More generally, when all requirements equal kk, we show how the cost changes when the algorithm provides any number q≤kq \le k of paths: what matters is the slack k−q+1k-q+1. Whether exact connectivity admits a competitive ratio polylogarithmic in nn remains open.

Preliminaries

The input is a known loopless undirected multigraph G=(V,E)G=(V,E) with n=∣V∣≥2n=|V|\ge2 vertices and m=∣E∣m=|E| edges. Parallel edges are allowed. Each edge ee has a nonnegative rational cost cec_e, and for a set of edges FF we write c(F)=∑e∈Fcec(F)=\sum_{e\in F}c_e. Each edge has unit capacity and can be bought at most once. Edges with the same two endpoints form a parallel bundle. We identify a set of edges with the spanning subgraph of GG that it forms; in particular, connectivity in a set of bought edges HH refers to the graph (V,H)(V,H). For a vector y∈REy\in\mathbb{R}^E and F⊆EF\subseteq E we write y(F)=∑e∈Fyey(F)=\sum_{e\in F}y_e and c⊤y=∑e∈Eceyec^\top y=\sum_{e\in E}c_ey_e. Throughout, log⁡\log is to an arbitrary fixed base, ln⁡\ln is the natural logarithm, exp⁡(x)=ex\exp(x)=e^x, and 1[⋅]\mathbf{1}[\cdot] is the indicator of an event. The notation polylog⁡n\operatorname{polylog} n means (log⁡n)O(1)(\log n)^{O(1)}, and Oα(⋅)O_\alpha(\cdot) hides a factor depending only on the parameter α\alpha.

A shore is a set of vertices S⊆VS\subseteq V. For a subgraph JJ of GG, the set δJ(S)\delta_J(S) consists of the edges of JJ with exactly one endpoint in SS. A shore SS separates two vertices u,vu,v if it contains exactly one of them. A uu–vv separator in JJ is a set of edges of JJ whose removal leaves no uu–vv path. A separator is identified by its edge set and a shore by its vertex set; in our parity construction these need not carry the same information. The connectivity λJ(u,v)\lambda_J(u,v) is the minimum size of a uu–vv separator in JJ; a separator of this size is a minimum separator. By the edge version of Menger’s theorem, this equals the maximum number of edge-disjoint uu–vv paths in JJ. A minimum-cut shore for u,vu,v in JJ is a shore SS separating u,vu,v with ∣δJ(S)∣=λJ(u,v)|\delta_J(S)|=\lambda_J(u,v). All connectivity computations use unit capacities on edges; costs are never used as capacities.

Requests (si,ti,ri)(s_i,t_i,r_i) arrive one at a time, for i=1,2,…i=1,2,\ldots. Each request has distinct endpoints si≠tis_i\ne t_i and a positive integer requirement rir_i. We assume the requests are feasible in GG, that is, λG(si,ti)≥ri\lambda_G(s_i,t_i)\ge r_i; thus every requirement is at most mm. Disconnected inputs are treated component-wise; we describe one connected component. The requests are rooted if all of them share a common endpoint. The first ii requests form the prefix ii. When describing an algorithm, we write (u,v)(u,v) for the pair of the request being processed. Requirements are uniform if all of them equal a common value kk, known in advance; in that case we write kk instead of rir_i. In general, kk refers to the largest requirement, which our nonuniform algorithm does not need to know. An online algorithm maintains a set HH of bought edges, which only grows. After request ii is processed we denote it by HiH_i, and the algorithm pays c(Hi)c(H_i) in total.

For a parameter 0<ϵ≤10<\epsilon\le1, a positive rational when supplied as input, the algorithm must ensure λHi(sj,tj)≥⌈rj/(1+ϵ)⌉\lambda_{H_i}(s_j,t_j)\ge\lceil r_j/(1+\epsilon)\rceil for every j≤ij\le i. We say that it violates the connectivity requirement by a factor of 1+ϵ1+\epsilon, and call 1+ϵ1+\epsilon its connectivity loss. Providing only half of each requirement corresponds to loss 2. For uniform requirements we also study an arbitrary integer target 1≤q≤k1\le q\le k, so that every requested pair must have connectivity at least qq in HH, and we call

σ=k−q+1\sigma= k-q+1

the slack. The headline case is q=⌈k/(1+ϵ)⌉q=\lceil k/(1+\epsilon)\rceil.

A request sequence is oblivious if it is fixed independently of all algorithmic randomness; expectations E[⋅]\mathbb{E}[\cdot] and probabilities P[⋅]\mathbb{P}[\cdot] are over the algorithm’s random choices. The cuts computed internally by the algorithm may depend on its complete purchase history.

For a prefix ii, let CiC_i be the set of shores separating at least one requested pair (sj,tj)(s_j,t_j) with j≤ij \le i. With common full requirement kk, define

LP⁡k(i)=min⁡{∑e∈Eceye:0≤ye≤1,y(δG(S))≥k for every S∈Ci}.(1)\operatorname{LP}_k(i)=\min\left\{\sum_{e\in E}c_e y_e: 0\le y_e\le1,\quad y(\delta_G(S))\ge k\ \text{for every }S\in C_i\right\}. \tag*{(1)}

Its integral counterpart, with ye∈{0,1}y_e\in\{0,1\}, is OPT⁡k(i)\operatorname{OPT}_k(i): the cost of the cheapest set of edges that gives every requested pair connectivity kk. The bounds ye≤1y_e\le1 reflect the unit capacities and are essential to our analysis. For nonuniform requests, LP⁡(i)\operatorname{LP}(i) and OPT⁡(i)\operatorname{OPT}(i) are defined in the same way, except that a shore separating (sj,tj)(s_j,t_j) must be crossed by mass at least rjr_j. In every case LP⁡(i)≤OPT⁡(i)\operatorname{LP}(i)\le\operatorname{OPT}(i). An algorithm is α\alpha-competitive if E[c(Hi)]≤αOPT⁡(i)\mathbb{E}[c(H_i)]\le\alpha\operatorname{OPT}(i) for every prefix ii of every oblivious sequence. All our bounds are stated against LP⁡\operatorname{LP}, which is stronger.

Let T⊆GT\subseteq G be a spanning tree. For vertices u,vu,v, let PT(u,v)P_T(u,v) be the unique uu–vv path in TT, and let dT(u,v)=c(PT(u,v))d_T(u,v)=c(P_T(u,v)) be its cost; tree edges keep their original costs. For an edge ee with endpoints uu and vv we write PT(e)=PT(u,v)P_T(e)=P_T(u,v) and dT(e)=dT(u,v)d_T(e)=d_T(u,v). An edge e∉Te\notin T is a chord, and its fundamental cycle is Ce={e}∪PT(e)C_e=\{e\}\cup P_T(e). A polynomial-time spanning-tree sampler has stretch D(n)D(n) if it outputs a random spanning tree T⊆GT\subseteq G satisfying

ET[dT(u,v)]≤D(n)ce(e=uv∈E).(2)\mathbb{E}_T[d_T(u,v)]\le D(n)c_e\qquad(e=uv\in E). \tag*{(2)}

We take D(n)≥1D(n)\ge1. A spanning tree TT is sampled when it is drawn from such a sampler; all later random choices are independent of it. In the headline bounds we use D(n)=O(log⁡(n+1))D(n)=O(\log(n+1)) from [3]; the full tradeoff below keeps D(n)D(n) explicit. Our direct-cut algorithm does not use the sampler.

Our results

Theorem 1.1 (Uniform requirements). For every 0<ε≤10<\varepsilon\le1 and known common requirement kk, there is a randomized polynomial-time online algorithm that always provides q=⌈k/(1+ε)⌉q=\lceil k/(1+\varepsilon)\rceil edge connectivity for all arrived pairs. For every fixed prefix ii of an oblivious request sequence,

E[c(Hi)]≤O(log⁡(n+1)εmin⁡{log⁡(n+1)log⁡(2+nk),1+nk})LP⁡k(i).(3)\mathbb{E}[c(H_i)]\le O\left(\frac{\log(n+1)}{\varepsilon}\min\left\{\log(n+1)\log\left(2+\frac{n}{k}\right),1+\frac{n}{k}\right\}\right)\operatorname{LP}_k(i). \tag*{(3)}

This holds for arbitrary multigraphs. In particular, if k≥αnk\ge\alpha n for a fixed α>0\alpha>0, the competitive ratio is Oα(ε−1log⁡(n+1))O_\alpha(\varepsilon^{-1}\log(n+1)) and is independent of the spanning-tree sampler.

The graph, kk, and ε\varepsilon determine which of our two algorithms is used; the choice is made before the requests arrive. One factor log⁡(n+1)\log(n+1) in (3) comes from discarding all but the kk cheapest edges in each parallel bundle, a reduction that preserves both benchmarks. Before this reduction we prove the following more precise tradeoff.

Theorem 1.2 (The full connectivity–cost tradeoff). Fix integers 1≤q≤k1\le q\le k. For a common full requirement kk, the parity-cover algorithm supplies qq connectivity at expected cost at most

O(D(n)[1k+q−1k−q+1log⁡(2+nq)log⁡(1+mq)])LP⁡k(i).(4)O\left(D(n)\left[\frac{1}{k}+\frac{q-1}{k-q+1}\log\left(2+\frac{n}{q}\right)\log\left(1+\frac{m}{q}\right)\right]\right)\operatorname{LP}_k(i). \tag*{(4)}

For q=1q = 1, its bound is exactly D(n)LP⁡k(i)/kD(n)\operatorname{LP}_{k}(i)/k. The direct-cut algorithm supplies the same target at expected cost at most

O(n+qk−q+1log⁡(1+mn+q))LP⁡k(i).(5)O\left(\frac{n+q}{k-q+1}\log\left(1+\frac{m}{n+q}\right)\right)\operatorname{LP}_{k}(i). \tag*{(5)}

Both algorithms are polynomial time, are feasible on every execution, and satisfy the displayed bound at every fixed oblivious prefix.

The denominator k−q+1k-q+1 in both bounds is the slack σ\sigma. At q=kq = k, the parity bound still has a factor k−1k-1. Thus the endpoint of the theorem is a polynomial implementation of an exact-connectivity guarantee with this dependence; it does not give an exact o(k)o(k) polylog nn result in general.

Theorem 1.3 (Nonuniform requirements). For arbitrary online requests (si,ti,ri)(s_i,t_i,r_i) and fixed 0<ε≤10 < \varepsilon\le1, there is a randomized polynomial-time algorithm that always provides ⌈ri/(1+ε)⌉\lceil r_i/(1+\varepsilon)\rceil edge connectivity for each request and satisfies

E[c(Hi)]≤O(log⁡(n+1)log⁡2(m+1)ε)LP⁡(i)(6)\mathbb{E}[c(H_i)] \le O\left(\frac{\log(n+1)\log^{2}(m+1)}{\varepsilon}\right)\operatorname{LP}(i) \tag*{(6)}

at every fixed prefix of an oblivious sequence. No upper bound on future requirements is needed. In particular, the competitive ratio has no additional factor depending on the maximum requirement.

For the original vertex-arrival formulation, take the first terminal as a root and request a pair between that root and every later terminal. Providing qq connectivity from every terminal to the root provides qq connectivity between every two terminals: a cut separating two terminals separates at least one of them from the root. Thus our arbitrary-pair theorems include that formulation.

The logarithmic spanning-tree theorem of Hajiaghayi [3] provides a polynomial-time construction with D(n)=O(log⁡(n+1))D(n) = O(\log(n+1)). This is the tree input used in Theorems 1.1 and 1.3. Consequently, uniform requests on arbitrary multigraphs, and nonuniform requests on simple graphs, both admit a competitive ratio of O(ε−1log⁡3(n+1))O(\varepsilon^{-1}\log^{3}(n+1)). The stronger connectivity-dependent bound in (3) applies to the uniform case.

This stretch matches the Ω(log⁡n)\Omega(\log n) lower bound of Alon, Karp, Peleg, and West [4], which already holds for the average stretch of a single spanning tree. The result of [3] is an external input to this paper. The proof of Theorem 1.2 works with any sampler satisfying (2). For completeness, Appendix A also records how the published average-stretch bound of Abraham and Neiman [5] yields such a sampler. The main approximation bounds use the logarithmic theorem of [3]; with the Abraham–Neiman bound instead, every use of D(n)D(n) costs an additional factor O(log⁡log⁡n)O(\log\log n).

Comparison and related work

Table 1 records the main comparison. Our improvement is in the permitted connectivity loss, in the treatment of arbitrary requirements, and in the dependence on connectivity within the new tradeoff. For example, the deterministic O(log⁡n)O(\log n) competitive ratio of [2] for rooted uniform requests remains better at loss two in some parameter ranges. We do not improve every earlier special case.

Online Steiner tree and forest are the requirement-one cases, studied by Imase and Waxman [6] and Berman and Coulston [7], among others. Offline survivable network design admits Jain’s factor-two approximation [8]. In the online setting, a logarithmic lower bound is already known for rooted requirement two [1 Appendix A]. Naor, Umboh, and Williamson [9] improved the special case of maximum requirement two through online weighted tree augmentation.

ResultRequestsLossCompetitive ratio
Gupta et al. [1]General, maximum kkNoneO(klog⁡3n)O(k\log^{3} n)
Dehghani et al. [2]Uniform, rooted2O(log⁡n)O(\log n)
Dehghani et al. [2]Uniform, arbitrary pairs2O(log⁡2n)O(\log^{2} n)
This paperUniform, arbitrary pairs1+ε1+\varepsilon(3); O(ε−1log⁡n)O(\varepsilon^{-1}\log n) if k=Ω(n)k=\Omega(n)
This paperNonuniform, arbitrary pairs1+ε1+\varepsilonO(ε−1log⁡(n+1)log⁡2(m+1))O(\varepsilon^{-1}\log(n+1)\log^{2}(m+1))

Table 1. All cost bounds use the optimum for the full requirements. The guarantees of this paper hold against the capacitated cut LP. Our algorithms are randomized against oblivious arrivals; the cited loss-two algorithms are deterministic.

For nonuniform requirements, the bicriteria framework of [2] incurs a factor log⁡1+δk\log^{1+\delta} k in the maximum requirement kk and loss 2+δ2+\delta for a constant δ>0\delta>0. Our nonuniform algorithm handles all requirements in one covering process. Its proof uses residual multiplicities instead of partitioning requests into requirement classes.

Online covering and primal–dual growth are standard tools [10, 11]. Borst, Eliáš, and Venzin [12] use a model of semi-adaptive adversaries as a key ingredient for online node-weighted Steiner forest. Our analysis faces a related issue: a minimum cut depends on previous random purchases, so we prove one exponential-moment inequality for each member of a fixed shore family. The new quantitative ingredients are the multiplicity discount, the coordinate cap, and the connectivity-rank bound on the number of repairs.

Fixed-base connectivity augmentation has also seen recent progress. Garg and Subramanian [13] study online augmentation of a given kk-edge-connected graph, where each arriving pair must become (k+1)(k+1)-edge-connected; they obtain deterministic O(log⁡n)O(\log n) and, for weighted links, O(log⁡2n)O(\log^{2} n) competitive ratios. Garg, Hommelsheim, and Lindermayr [14] obtain a deterministic O(log⁡n)O(\log n) weighted bound for pair arrivals. Hathcock, Subramanian, Umboh, and Zlatin [15] obtain nearly logarithmic weighted bounds in the cut-arrival model. These results start from a fixed globally kk-edge-connected graph. Our bought graph grows with the requests, and unrequested Steiner vertices need not have high connectivity.

Finally, (2) requires spanning trees made of input edges. A distribution over arbitrary tree metrics, such as the Fakcharoenphol–Rao–Talwar embedding [16], does not by itself provide the physical cycles used in our algorithm.

Our Approach and Techniques

From deficient cuts to many interchangeable witnesses

Fix a common full requirement kk, and suppose we only need to provide q≤kq\le k connectivity. Write

σ=k−q+1.\sigma= k-q+1.

The central observation is that a cut of the bought graph with ℓ<q\ell<q edges leaves at least k−ℓ≥σk-\ell\ge\sigma choices in any full-kk solution. To exploit those choices, however, we need a covering constraint that does not depend on unbought parts of the network in an uncontrolled way. The parity construction supplies such a constraint while retaining all k−ℓk-\ell witnesses.

Parity labels and a fundamental cycle

Figure 1. A chord joining opposite parity classes has a fundamental cycle with odd intersection with QQ. The path shown has three edges of QQ; only their parity matters. The shore SQS_Q need not be a minimum-cut shore of the bought graph.

Sample one spanning tree TT at the beginning. On a request (u,v)(u,v), buy the tree path PT(u,v)P_T(u,v). The remaining decisions are purchases of fundamental cycles

Ce={e}∪PT(e),e∉T,C_e=\{e\}\cup P_T(e), \qquad e\notin T,

at prices de=ce+dT(e)d_e=c_e+d_T(e). These prices may overcount previously bought edges, which is harmless. They also give a fixed price to each of at most mm choices. Expected tree stretch will later compare their prices with the original cost of one fixed offline solution.

Suppose the bought graph HH still has an uu–vv minimum separator QQ of size ℓ<q\ell<q. Root TT at a reference vertex. Give each vertex the parity of the number of edges of Q∩TQ\cap T on its path from the reference vertex, and let SQS_Q be the vertices with odd parity. The already bought uu–vv tree path meets QQ oddly, so SQS_Q separates the requested pair. A chord in

AQ=δG(SQ)∖QA_Q=\delta_G(S_Q)\setminus Q

has a fundamental cycle that meets QQ oddly. Purchasing that cycle destroys QQ as a separator. The reason is elementary but useful: if QQ remained a separator, its minimum cardinality would force it to be a cut of the enlarged graph, whereas every cycle crosses a cut an even number of times.

Every full-kk solution FF has at least kk edges across SQS_Q. Deleting QQ excludes at most ℓ\ell of them. Hence

∣F∩AQ∣≥k−ℓ≥σ.(7)|F\cap A_Q|\ge k-\ell\ge\sigma. \tag*{(7)}

Putting value 1/σ1/\sigma on every comparator chord gives one fractional cover of every row the algorithm may expose. For a cut-LP solution yy, the same calculation is y(AQ)≥k−y(Q)≥k−ℓy(A_Q)\ge k-y(Q)\ge k-\ell, so the comparison extends to ye/σy_e/\sigma. This is the source of the improvement as the target falls below kk. We use all available witnesses, even though the algorithm only has to buy one cycle to destroy the current separator.

Why capping helps both the algorithm and the bound

The rows are not listed in advance. The algorithm finds one deficient cut, forms its parity row by a tree traversal and an edge scan, and processes that row. A fractional variable xex_e records investment in cycle ee. On an unhit row AA, the update is a cost-scaled multiplicative increase with a small additive seed:

Δxe=γde(xe+1m).\Delta x_e = \frac{\gamma}{d_e}\left(x_e+\frac{1}{m}\right).

Each increase also offers a fresh chance to buy the cycle, with probability proportional to aΔxea\Delta x_e. Here aa is an amplification parameter determined by how many different shores may witness a repair. A coordinate is frozen after its cycle is bought.

The crucial additional rule is deterministic: buy a cycle as soon as xex_e reaches 1/a1/a. Thus the fractional process never needs to invest substantially beyond the scale at which rounding should have selected the cycle. Allowing a constant overshoot gives xe≤3/(2a)x_e \le3/(2a). The usual multiplicative-growth calculation then bounds the total dual load on an edge by

O(delog⁡(1+m/a)).O\left(d_e\log(1+m/a)\right).

instead of O(delog⁡m)O(d_e\log m). Combining this with (7) gives fractional cost O(log⁡(1+m/a))∑e∈F∖Tde/σO(\log(1+m/a))\sum_{e\in F\setminus T}d_e/\sigma. Random purchases and threshold purchases multiply this bound by O(a)O(a). The resulting expression is

O(alog⁡(1+m/a)σ)∑e∈F∖Tde.O\left(\frac{a\log(1+m/a)}{\sigma}\right)\sum_{e\in F\setminus T}d_e.

It remains to justify a small enough amplification parameter despite the dependence of future cuts on past purchases.

Counting tree shores instead of failed edge sets

A direct union bound over all separators QQ would count subsets of mm edges. The parity shore depends only on Q∩TQ\cap T, so a much smaller description uses subsets of the n−1n-1 tree edges. The nontrivial issue is that many different rows can have the same parity shore: they can exclude different bought chords. We therefore track two quantities for each fixed shore SS:

XS=∑e∈δG(S)∖Txe,YS=∣I∩δG(S)∣.X_S=\sum_{e\in\delta_G(S)\setminus T}x_e,\qquad Y_S=\lvert I\cap\delta_G(S)\rvert.

where II is the set of selected chords. Fractional investment increases XSX_S, while actual purchases increase YSY_S. With β=1−e−1\beta=1-e^{-1}, the process

ZS=exp⁡(βaXS−YS)(8)Z_S=\exp(\beta aX_S-Y_S) \tag*{(8)}

is a nonnegative supermartingale. Fresh independent coins make the expected decrease caused by purchases cancel the increase caused by fractional growth. Deterministic purchases can only decrease it. This calculation is conditional on the entire history, and therefore allows the next row to be chosen adaptively.

If a row reaches mass one without selecting a cycle, we force a cheapest purchase. At that moment XSQ≥1X_{S_Q}\ge1. Moreover, every already selected chord crossing SQS_Q belongs to QQ: otherwise its cycle would already have destroyed the separator. Thus YSQ≤q−1Y_{S_Q}\le q-1. A forced repair requires the fixed-shore process (8) to reach at least exp⁡(βa−q+1)\exp(\beta a-q+1).

There are only

NT=∑j=1min⁡{q−1,n−1}(n−1j)N_T=\sum_{j=1}^{\min\{q-1,n-1\}}\binom{n-1}{j}

possible nontrivial parity shores. A maximal inequality and a union bound over these fixed shores control all adaptive repairs at once. We never enumerate the shores. Their number determines aa, and only its logarithm appears in the cost.

One more observation is needed on multigraphs. Bounding the number of repairs merely by mm would introduce an unnecessary log⁡m\log m term into the probability budget. In the virtual graph T∪IT \cup I, consider, for every level h=2,…,qh = 2, \ldots, q, the partition into hh-edge-connectivity classes. The first new chord selected while processing a row joins vertices with connectivity below qq. Adding that chord merges two classes at some level. The sum of the numbers of such mergers is at most (q−1)(n−1)(q-1)(n-1). This gives a deterministic bound on all row procedures, including forced repairs, that depends on vertices and connectivity rather than on parallel multiplicity.

Consequently we can take a=O(qlog⁡(2+n/q))a = O(q \log(2+n/q)). Together with a≥qa \ge q, the cap gives the product

log⁡(2+nq)log⁡(1+mq)(9)\log\left(2+\frac{n}{q}\right)\log\left(1+\frac{m}{q}\right) \tag*{(9)}

in (4). Finally, requested tree paths cost at most 1/k1/k times the comparator’s total tree distance: each used tree edge defines a cut crossed by at least kk comparator edges. Averaging the cycle and path charges over TT contributes D(n)D(n).

The second algorithm: pay for all shores and avoid the tree

The parity construction reduces the number of shores, but it pays for fundamental cycles. When kk is large, we can afford a larger shore family and save that tree cost entirely.

For this algorithm, take an actual deficient minimum-cut shore SS of the bought graph and expose

A=δG(S)∖H.A = \delta_G(S) \setminus H.

The objects are now individual edges, at their original prices. Every full-kk comparator again contributes at least k−∣δH(S)∣≥σk - |\delta_H(S)| \ge\sigma available edges. Run exactly the same capped growth and purchase procedure on AA. An edge in AA increases the size of this particular cut; the algorithm then recomputes a minimum cut until the request is served.

There are fewer than 2n−12^{n-1} canonical vertex shores. At a forced repair, at most q−1q-1 bought edges cross its shore, so the same potential (8) applies. The connectivity partition potential now includes level one, allowing the bought graph to begin disconnected. It bounds the number of procedures by q(n−1)q(n-1). An amplification of a=Θ(n+q)a = \Theta(n+q) therefore suffices. The capped-growth bound becomes

O(n+qk−q+1log⁡(1+mn+q))LPk.O\left(\frac{n+q}{k-q+1}\log\left(1+\frac{m}{n+q}\right)\right)\mathrm{LP}_k.

The factor nn comes from the logarithm of the number of shores, and the denominator comes from the number of comparator witnesses. For q=⌈k/(1+ε)⌉q = \lceil k/(1+\varepsilon)\rceil and k=Ω(n)k = \Omega(n), those factors cancel up to O(1/ε)O(1/\varepsilon). This explains the logarithmic cost bound without a tree-embedding factor.

Nonuniform requirements in one covering process

For a request of requirement rr and a deficient cut of size ℓ\ell, the parity row contains comparator mass at least b=r−ℓb = r-\ell. Rather than normalize every row by a common slack, we grow its fractional mass toward bb, using an additive seed b/mb/m. The dual objective charges that update in proportion to bb. At the relaxed target,

ℓ≤r1+ε⟹b≥εℓ.\ell\le\frac{r}{1+\varepsilon} \quad\Longrightarrow\quad b \ge\varepsilon\ell.
Comparison of parity cover and direct cuts algorithms

Figure 2. The two algorithms make complementary choices. The first compresses the shore family using a tree; the second avoids the cost of tree paths. Their quantitative bounds can be compared before the arrival sequence begins.

Thus a repair at a separator of size ℓ\ell requires investment exceeding εℓ\varepsilon\ell. The probability of such an event decreases exponentially in ℓ\ell, while the number of formal separators of size ℓ\ell is at most mℓm^\ell. Choosing amplification O(ε−1log⁡(m+1))O(\varepsilon^{-1}\log(m+1)) makes the sum over all separator sizes converge. This is why no requirement classes, advance maximum, or extra logarithm in the maximum requirement are needed.

Preliminaries and purchase accounting

For a graph JJ, let δJ(S)\delta_J(S) be its edges with exactly one endpoint in SS, and let λJ(u,v)\lambda_J(u,v) be the minimum size of an uu–vv edge cut. By the edge version of Menger’s theorem, this is also the maximum number of edge-disjoint paths. Costs are not capacities: all connectivity computations use unit capacities on bought edges. A separator is identified by its edge set; a shore is identified by a subset of vertices. These need not carry the same information in the parity construction.

The algorithm’s bought graph is always the union of its purchases. For the parity algorithm, selecting chord ee means buying every missing edge of CeC_e. We charge the full price de=ce+dT(e)d_e=c_e+d_T(e), even when part of that cycle is already present. Each selected chord is recorded once in II. Requested tree paths are charged separately by the cost of their union. Thus these charges are an upper bound on the amount actually paid.

Zero costs. Buy all zero-cost edges initially. For the parity algorithm, 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. Every zero-cost edge then has a zero-cost tree path. Include all zero-price chords in II initially. A violated row never contains an object already selected, so all update denominators are positive. The original vertices and all unit-capacity edges are kept for connectivity computations. Contracting zero-cost components in those computations would be incorrect.

Fixed-prefix comparisons. Throughout a cost proof, fix a finite prefix of the external sequence and one feasible vector yy for its full-requirement cut LP. This vector is independent of the sampled tree and all purchase coins. It is used only in the analysis. The algorithm never needs the future prefix, an optimum, or the value of LP.

Algorithm 1: CoverRow($A$): shared capped purchase procedure
Input: A nonempty row $A \subseteq U \setminus I$; fixed prices $d_e > 0$.
1: while $A \cap I = \varnothing$ and $\sum_{e \in A} x_e < 1$ do
2: $\gamma \leftarrow (\eta/4)\min_{e \in A} d_e$.
3: Compute $\Delta_e \leftarrow (\gamma/d_e)(x_e + 1/m)$ for every $e \in A$.
4: $x_e \leftarrow x_e + \Delta_e$ for every $e \in A$, simultaneously.
5: Independently mark each $e \in A$ with probability $\operatorname{Dyad}(\min\{1,a\Delta_e\})$.
6: Select every marked object and insert it into $I$.
7: Select every remaining $e \in A$ with $x_e \ge 1/a$; insert it into $I$.
8: Finish this entire batch before inspecting another row.
9: if $A \cap I = \varnothing$ then
10: Select a minimum-price object of $A$ and insert it into $I$. \{forced repair\}

Capped covering with adaptively exposed rows

We prove the common rounding lemma once. Let UU be a fixed set of at most mm objects with positive prices ded_e. The algorithm maintains an initially empty selected set II on its positive-cost objects and nonnegative variables xex_e, initially zero. A coordinate stops changing once its object is selected. A row is a nonempty set A⊆U∖IA \subseteq U \setminus I; rows may depend on the entire preceding history.

Fix an integer amplification a≥1a \ge1, and put

η=min⁡{1,m/a},B(a)=54ln⁡(1+3m2a),β=1−e−1.(10)\eta= \min\{1,m/a\}, \qquad B(a) = \frac{5}{4}\ln\left(1+\frac{3m}{2a}\right), \qquad\beta= 1-e^{-1}. \tag*{(10)}

For 0<p≤10 < p \le1, let Dyad⁡(p)\operatorname{Dyad}(p) be the smallest number of the form 2−h2^{-h}, h∈Z≥0h \in\mathbb{Z}_{\ge0}, that is at least pp; set Dyad⁡(0)=0\operatorname{Dyad}(0)=0. The selection rule is explicit and uses only fair random bits.

After conditioning on any preprocessing randomness, all prices, shore incidences, and parameters below are fixed. We assume that, in the prefix under analysis, one fixed nonnegative vector zz, independent of the subsequent purchase coins, satisfies z(A)≥1z(A) \ge1 for every row that can be exposed. Here qq, RR, and NN are positive integers. We also assume a deterministic upper bound RR on the number of row procedures. To bound repairs, associate each row with a member of a fixed family S\mathcal{S} of size at most NN. Each member SS has a fixed incident object set US⊆UU_S \subseteq U. At every forced repair of row AA associated with SS, require

A⊆US,∣I∩US∣≤q−1.(11)A \subseteq U_S, \qquad|I \cap U_S| \le q-1. \tag*{(11)}

These hypotheses concern only the repair state. The family can be exponential and need not be generated.

Lemma 4.1 (Capped adaptive covering). Under the preceding assumptions, if

Nexp⁡(−βa+q−1)≤12R,(12)N\exp(-\beta a+q-1) \le\frac{1}{2R}, \tag*{(12)}

then Algorithm 1 has expected total selection price at most

(6aB(a)+12)dTz.(13)\left(6aB(a)+\frac{1}{2}\right)d^{\mathsf T}z. \tag*{(13)}

Every call selects a new object, and each call performs O(log⁡(m+1))O(\log(m+1)) updates for every a≥1a \ge1.

Fractional growth and the cap

An active coordinate is below 1/a1/a. Since η≤1\eta\le1 and η≤m/a\eta\le m/a, a simultaneous update satisfies

Δe<η4(1a+1m)≤12a.(14)\Delta_e < \frac{\eta}{4}\left(\frac{1}{a}+\frac{1}{m}\right) \le\frac{1}{2a}. \tag*{(14)}

Consequently xe<3/(2a)x_e < 3/(2a) at all times and aΔe≤1/2a\Delta_e \le1/2. A coordinate that crosses its threshold is immediately selected and frozen. If πe\pi_e is its fresh coin probability, then

aΔe≤πe≤2aΔe,1−πe≤exp⁡(−aΔe).(15)a\Delta_e \le\pi_e \le2a\Delta_e,\qquad1-\pi_e \le\exp(-a\Delta_e). \tag*{(15)}

Let X=∑edexeX=\sum_e d_e x_e. Assign a dual charge γj\gamma_j to each fractional update jj on row AjA_j. For a fixed object ee, the update identity is

1+mxe=∏j:e∈Aj(1+γjde).1+mx_e=\prod_{j:e\in A_j}\left(1+\frac{\gamma_j}{d_e}\right).

Because 0≤γj/de≤1/40\le\gamma_j/d_e\le1/4 and ln⁡(1+t)≥4t/5\ln(1+t)\ge4t/5 on this interval,

∑j:e∈Ajγj≤54deln⁡(1+mxe)≤B(a)de.(16)\sum_{j:e\in A_j}\gamma_j\le\frac{5}{4}d_e\ln(1+mx_e)\le B(a)d_e. \tag*{(16)}

Each update begins with x(Aj)<1x(A_j)<1, so

ΔX=γj(x(Aj)+∣Aj∣m)<2γj.\Delta X=\gamma_j\left(x(A_j)+\frac{|A_j|}{m}\right)<2\gamma_j.

Using z(Aj)≥1z(A_j)\ge1 and summing gives the pathwise inequality

X≤2∑jγj≤2∑eze∑j:e∈Ajγj≤2B(a)dTz.(17)X\le2\sum_j\gamma_j\le2\sum_e z_e\sum_{j:e\in A_j}\gamma_j\le2B(a)d^{\mathsf T}z. \tag*{(17)}

The rows need not all become fractionally covered. An early integral purchase may end a row procedure before its mass reaches one; the dual-load argument still applies.

Conditional on the history just before an update, its expected coin purchase price is at most 2aΔX2a\Delta X, by (14). The total threshold price is at most aXaX on each execution, since every threshold purchase has xe≥1/ax_e\ge1/a and occurs only once. Thus these two types of purchases have expected price at most 3aE[X]≤6aB(a)dTz3a\mathbb{E}[X]\le6aB(a)d^{\mathsf T}z.

One exponential moment for each fixed shore

Fix S∈SS\in\mathcal{S} and consider checkpoints after each complete update-and-purchase batch and immediately before each forced repair. Define

XS=∑e∈USxe,YS=∣I∩US∣,ZS=exp⁡(βaXS−YS).X_S=\sum_{e\in U_S}x_e,\qquad Y_S=|I\cap U_S|,\qquad Z_S=\exp(\beta aX_S-Y_S).

The increments are determined before the fresh coins. A coordinate is updated only when unselected. For each updated incident object, its independent coin gives a purchase indicator with probability πe≥aΔe\pi_e\ge a\Delta_e. Therefore

E[e−ΔYS∣preceding history]≤∏e∈US(1−βπe)≤exp⁡(−βa∑e∈USΔe).\mathbb{E}\left[e^{-\Delta Y_S}\mid\text{preceding history}\right]\le\prod_{e\in U_S}(1-\beta\pi_e)\le\exp\left(-\beta a\sum_{e\in U_S}\Delta_e\right).

The first inequality allows additional threshold purchases. This cancels the factor from the increase of XSX_S. Forced purchases also only decrease ZSZ_S. Hence ZSZ_S is a nonnegative supermartingale with initial value at most one.

At a forced repair, the current row has mass at least one. By (10), its associated shore has XS≥1X_S \ge1 and YS≤q−1Y_S \le q-1. Thus ZS≥exp⁡(βa−q+1)Z_S \ge\exp(\beta a-q+1). The maximal inequality for a nonnegative supermartingale, followed by a union bound over the fixed shore family, yields

P(some forced repair)≤Nexp⁡(−βa+q−1)≤12R.(18)\mathbb{P}(\text{some forced repair}) \le N\exp(-\beta a+q-1) \le\frac{1}{2R}. \tag*{(18)}

For a direct proof of the maximal inequality here, stop the process at the first threshold crossing or at the last checkpoint. Its expectation is at most one, so the crossing probability is at most the reciprocal of the threshold. The number of updates is bounded deterministically below, and no limiting stopping argument is needed.

Since z(A)≥1z(A) \ge1, the cheapest object of any exposed row costs at most dTzd^{\mathsf{T}}z. At most RR repairs occur. Their total price is therefore at most RdTzRd^{\mathsf{T}}z on any execution and is zero unless the event in (17) occurs. Its expectation is at most dTz/2d^{\mathsf{T}}z/2. Together with (16), this proves the cost bound.

Termination of a row procedure

Within one row AA, fix a cheapest member e0e_0. Until the procedure ends, every update multiplies xe0+1/mx_{e_0}+1/m by 1+η/41+\eta/4. Starting from zero, it reaches the threshold 1/a1/a within

⌈ln⁡(1+m/a)ln⁡(1+η/4)⌉(19)\left\lceil\frac{\ln(1+m/a)}{\ln(1+\eta/4)} \right\rceil \tag*{(19)}

updates, unless another purchase or a forced repair ends the row earlier. If a≤ma \le m, then η=1\eta=1, so the bound is O(log⁡(m+1))O(\log(m+1)). If a>ma>m, put t=m/a∈(0,1)t=m/a\in(0,1). The inequality (1+t/4)4≥1+t(1+t/4)^4\ge1+t shows that at most four updates suffice. This completes the proof of Lemma 4.1.

The parity-cover algorithm

Fix a sampled tree TT, rooted at a reference vertex v0v_0. For any edge set QQ, define

χQ(v)=∣PT(v0,v)∩Q∣(mod2),SQ={v:χQ(v)=1},AQ=δG(SQ)∖Q.(20)\chi_Q(v)=\lvert P_T(v_0,v)\cap Q\rvert\pmod2,\qquad S_Q=\{v:\chi_Q(v)=1\},\qquad A_Q=\delta_G(S_Q)\setminus Q. \tag*{(20)}

The identity

δT(SQ)=Q∩T(21)\delta_T(S_Q)=Q\cap T \tag*{(21)}

holds for every QQ: the parity label flips across exactly those tree edges that belong to QQ.

Lemma 5.1 (Parity and multiplicity). Suppose HH contains PT(u,v)P_T(u,v) and every cycle CeC_e for e∈Ie\in I. Let QQ be a minimum uu–vv separator of HH, of size ℓ\ell. Then SQS_Q separates u,vu,v, all members of AQA_Q are chords, and AQ∩I=∅A_Q\cap I=\varnothing. Adding CeC_e for any e∈AQe\in A_Q destroys QQ as a separator. Every feasible full-kk cut vector yy for this request satisfies

y(AQ)≥k−ℓ.(22)y(A_Q)\ge k-\ell. \tag*{(22)}

Proof. Let UU be the vertices reachable from uu in H−QH-Q. Then δH(U)⊆Q\delta_H(U)\subseteq Q; minimum cardinality gives equality. The bought tree path from uu to vv crosses this cut oddly, so χQ(u)≠χQ(v)\chi_Q(u)\ne\chi_Q(v). By (20), a tree edge outside QQ has equal labels at its endpoints. Thus AQA_Q contains only chords.

Algorithm 2: Uniform parity cover for a common full requirement kk and target qq

  1. Sample T⊆GT \subseteq G satisfying (2); choose a reference root v0v_0.

  2. Buy zero-cost edges; put their zero-price chords into II.

  3. For every other chord ee, set de←ce+dT(e)d_e \leftarrow c_e + d_T(e) and xe←0x_e \leftarrow0.

  4. If q≥2q \ge2, set a←aTa \leftarrow a_T and η←min⁡{1,m/a}\eta\leftarrow\min\{1,m/a\} from Section 9.

  5. for each arriving pair (u,v)(u,v) do

  6. Buy every missing edge of PT(u,v)P_T(u,v).

  7. while λH(u,v)<q\lambda_H(u,v) < q do

  8. Compute a minimum uu–vv separator QQ in HH.

  9. Traverse TT to compute χQ\chi_Q and SQS_Q in (19).

  10. Form AQA_Q by scanning EE; call CoverRow⁡(AQ)\operatorname{CoverRow}(A_Q).

  11. A selected object ee buys the whole cycle CeC_e.

For e∈AQe \in A_Q with endpoints u′,v′u',v', its fundamental cycle satisfies

∣Ce∩Q∣=∣PT(u′,v′)∩Q∣≡χQ(u′)+χQ(v′)≡1(mod2).|C_e \cap Q| = |P_T(u',v') \cap Q| \equiv\chi_Q(u')+\chi_Q(v') \equiv1 \pmod{2}.

Suppose QQ still separated u,vu,v in J=H∪CeJ=H\cup C_e, and let U′U' be the vertices reachable from uu in J−QJ-Q. Then

ℓ≤∣δH(U′)∣≤∣δJ(U′)∣≤∣Q∣=ℓ.\ell\le|\delta_H(U')| \le|\delta_J(U')| \le|Q|=\ell.

It follows that δJ(U′)=Q\delta_J(U')=Q, contradicting the even intersection of a cycle and a cut. In particular, a cycle already contained in HH cannot have its chord in AQA_Q.

Finally, SQS_Q separates the request, so y(δG(SQ))≥ky(\delta_G(S_Q)) \ge k. Removing QQ loses at most ∣Q∣|Q| units because ye≤1y_e \le1. This proves (21). □

The loop recomputes a minimum cut after each call. Repairing one separator need not increase the minimum-cut value immediately. For q=1q=1, only requested tree paths are purchased.

A bound on the number of row procedures

For an integer h≥1h \ge1, the relation u∼hvu \sim_h v if u=vu=v or λJ(u,v)≥h\lambda_J(u,v) \ge h is an equivalence relation on the vertices of any undirected graph JJ. For transitivity, every cut separating u,wu,w separates at least one of the pairs u,vu,v and v,wv,w. Let κh(J)\kappa_h(J) be the number of equivalence classes. Adding edges only merges classes.

Lemma 5.2 (Connectivity-rank bound). For q≥2q \ge2, the total number of row procedures in Algorithm 2 is at most

RT=min⁡{m,(q−1)(n−1)}.(23)R_T=\min\{m,(q-1)(n-1)\}. \tag*{(23)}

Proof. Use the virtual graph K=T∪IK=T\cup I and the integer potential

ΦT(K)=∑h=2q(n−κh(K)).\Phi_T(K)=\sum_{h=2}^{q}(n-\kappa_h(K)).

It is nondecreasing and at most (q−1)(n−1)(q-1)(n-1). Immediately before the first new chord ee selected in a row for QQ, with endpoints u′,v′u',v',

δK(SQ)⊆Q.\delta_K(S_Q)\subseteq Q.

Indeed, (20) accounts for all crossing tree edges, and Lemma 5.1 forces all previously selected crossing chords into QQ. Thus 1≤h:=λK(u′,v′)≤∣Q∣<q1 \le h := \lambda_K(u',v') \le|Q| < q. Adding the edge ee increases every u′u'–v′v' cut by one, so the new connectivity is exactly h+1h+1. The (h+1)(h+1)-connectivity classes containing u′u' and v′v' merge, and ΦT\Phi_T increases by at least one. Further purchases cannot decrease it. Each procedure also selects a distinct chord, proving both bounds in (23). □

The virtual tree is used only in this proof. Its edges are paid for when requested paths or selected cycles use them; no free physical capacity is assumed.

Applying capped covering

Fix a prefix, its cut-LP comparator yy, and TT. Put σ=k−q+1\sigma= k-q+1 and

WT(y)=∑e∉Tdeye,ze=ye/σ(e∉T).(24)W_T(y)=\sum_{e\notin T}d_e y_e,\qquad z_e=y_e/\sigma\quad(e\notin T). \tag*{(24)}

By Lemma 5.1, zz covers every row. A canonical parity shore is determined by a nonempty subset of at most q−1q-1 tree edges, hence the shore family has size at most

NT=∑j=1min⁡{q−1,n−1}(n−1j).(25)N_T=\sum_{j=1}^{\min\{q-1,n-1\}}\binom{n-1}{j}. \tag*{(25)}

Restrict the covering universe and zz to positive-price chords; free chords were selected initially and never occur in a row. Take USU_S to be the positive-price chords in δG(S)∖T\delta_G(S)\setminus T. At a repair for QQ, its row is contained in USQU_{S_Q} and all selected chords crossing SQS_Q lie in QQ. More precisely,

∣I∩USQ∣≤∣Q∣−∣Q∩T∣≤q−2,|I\cap U_{S_Q}|\le|Q|-|Q\cap T|\le q-2,

because the requested tree path forces ∣Q∩T∣≥1|Q\cap T|\ge1. The weaker bound q−1q-1 suffices for Lemma 4.1. For an amplification satisfying (11) with N=NTN=N_T and R=RTR=R_T, the conditional expected cycle charge is at most

6aB(a)+1/2σWT(y).(26)\frac{6aB(a)+1/2}{\sigma}W_T(y). \tag*{(26)}

Let BiB_i be the union of requested tree paths in the prefix, excluding extra tree edges bought only through cycles. For each tree edge ff, let SfS_f be a component of T−fT-f. Double counting gives

∑e∈EyedT(e)=∑f∈Tcfy(δG(Sf))≥k c(Bi),(27)\sum_{e\in E}y_e d_T(e)=\sum_{f\in T}c_f y(\delta_G(S_f))\ge k\,c(B_i), \tag*{(27)}

since every f∈Bif\in B_i separates a requested pair. Averaging over TT yields

E[c(Hi)]≤[D(n)k+1+D(n)σ(6aB(a)+12)]c⊤y.(28)\mathbb{E}[c(H_i)]\le\left[\frac{D(n)}{k}+\frac{1+D(n)}{\sigma}\left(6aB(a)+\frac{1}{2}\right)\right]c^\top y. \tag*{(28)}

Here yy was fixed independently of TT, so E[∑eyedT(e)]≤D(n)c⊤y\mathbb{E}[\sum_e y_e d_T(e)]\le D(n)c^\top y and E[WT(y)]≤(1+D(n))c⊤y\mathbb{E}[W_T(y)]\le(1+D(n))c^\top y are legitimate applications of (2). Choosing an optimum yy proves the exact parameter form of the parity bound. Its simplification is given in § 9. Feasibility follows because every deficient request supplies a nonempty row and each call buys a new chord; by Lemma 5.2, the process cannot continue indefinitely.

Algorithm 3: Uniform direct cuts

  1. Buy all zero-cost edges; initialize I←∅I \gets\varnothing and xe←0x_e \gets0 on positive-cost edges.

  2. Set de←ced_e \gets c_e, a←a0a \gets a_0, and η←min⁡{1,m/a0}\eta\gets\min\{1,m/a_0\}.

  3. for each arriving pair (u,v)(u,v) do

    1. while λH(u,v)<q\lambda_H(u,v) < q do

      1. Compute a minimum uu–vv cut shore SS in HH.

      2. Set A←δG(S)∖HA \gets\delta_G(S) \setminus H.

      3. Call CoverRow(A)(A); selecting ee buys that original edge.

The direct-cut algorithm

There is no spanning tree in the second algorithm. Its objects are the original positive-cost edges, at prices de=ced_e = c_e. All zero-cost edges are present initially. Whenever a request (u,v)(u,v) has connectivity ℓ<q\ell< q, find an actual minimum-cut shore SS and expose

A=δG(S)∖H.(29)A = \delta_G(S) \setminus H. \tag*{(29)}

Run CoverRow on this row with amplification a0a_0 specified in Section 9. Selection buys the individual edge.

For any fixed full-kk cut vector yy,

y(A)≥y(δG(S))−∣δH(S)∣≥k−ℓ≥σ.y(A) \ge y(\delta_G(S)) - |\delta_H(S)| \ge k - \ell\ge\sigma.

Thus z=y/σz = y/\sigma covers every exposed row. To bound the number of procedures, use

Φ0(H)=∑h=1q(n−κh(H)).\Phi_0(H) = \sum_{h=1}^{q}(n-\kappa_h(H)).

For the first edge ee selected in a procedure, with endpoints u′,v′u',v', we have h=λH(u′,v′)≤ℓ<qh = \lambda_H(u',v') \le\ell< q. Adding ee merges the (h+1)(h+1)-connectivity classes of u′u' and v′v'. Therefore each procedure increases Φ0\Phi_0 by at least one. The number of procedures is at most

R0=min⁡{m,q(n−1)}.(30)R_0 = \min\{m,q(n-1)\}. \tag*{(30)}

Represent every nontrivial shore by its side excluding one fixed reference vertex. There are fewer than N0=2n−1N_0 = 2^{n-1} such shores. For each shore, take US=δG(S)U_S = \delta_G(S) restricted to positive-cost objects. At a forced repair, A⊆USA \subseteq U_S, and at most ∣δH(S)∣≤q−1|\delta_H(S)| \le q-1 selected objects cross SS. The hypotheses of Lemma 4.1 apply. With amplification satisfying (11), they give

E[c(Hi)]≤6a0B(a0)+1/2σ c⊤y.(31)\mathbb{E}[c(H_i)] \le\frac{6a_0B(a_0)+1/2}{\sigma}\,c^\top y. \tag*{(31)}

The choice a0=Θ(n+q)a_0 = \Theta(n+q) will prove (5). This algorithm has no tree charge.

Removing excess parallel edges

Lemma 6.1 (Parallel-bundle reduction). For a known common requirement kk, retain the kk cheapest edges of each parallel bundle, or the entire bundle when it has fewer than kk edges. This preserves LP⁡k(i)\operatorname{LP}_k(i) and OPT⁡k(i)\operatorname{OPT}_k(i) for every request prefix. The retained graph has at most m′≤k(k2)m' \le k\binom{k}{2} edges.

Algorithm 4: MultiCoverRow(A, b) for a nonuniform request

  1. while A∩I=∅A \cap I = \varnothing and w(A)<bw(A) < b do

  2. γ←14min⁡e∈Ade\gamma\gets\frac{1}{4}\min_{e\in A} d_e.

  3. Compute Δe←(γ/de)(we+b/m)\Delta_e \gets(\gamma/d_e)(w_e + b/m) for every e∈Ae \in A.

  4. Increase all wew_e simultaneously by Δe\Delta_e.

  5. Independently select each e∈Ae \in A with probability Dyad⁡(min⁡{1,a∗Δe})\operatorname{Dyad}(\min\{1,a_* \Delta_e\}).

  6. Buy every selected cycle, insert its chord into II, and finish the batch.

  7. if A∩I=∅A \cap I = \varnothing then

  8. Buy a cheapest cycle of AA and insert its chord into II.

Proof. For any feasible full-kk vector yy, let bb be its total mass in one bundle. Replace this mass by min⁡{k,b}\min\{k,b\}, assigned to the retained edges in nondecreasing cost order, at most one unit per edge. This does not increase cost. A cut contains either an entire bundle or none of it. If all its crossing bundles had mass less than kk, its total mass is unchanged. If some crossing bundle had mass at least kk, that bundle alone retains kk units. Thus every required cut stays feasible after all replacements. Conversely, a solution on retained edges is a solution on the original graph. The same argument preserves integrality because integer bundle masses are assigned integrally. This proves both equalities of optimum values and the edge-count bound. □

The reduction uses the known common requirement. We do not apply it to the nonuniform algorithm, whose future maximum is unknown.

Arbitrary requirements without requirement classes

We now prove Theorem 1.3. Keep the parity construction and cycle prices, but replace the uniform normalized process by fractional multicover growth. Fix ε\varepsilon, and let a∗a_* be the amplification chosen in Section 9. Initialize we=0w_e = 0 for every chord, and initialize II with all zero-price chords, whose cycles have been bought for free. As before, selected coordinates are frozen. On request (u,v,r)(u,v,r), first buy its tree path and set q=⌈r/(1+ε)⌉q = \lceil r/(1+\varepsilon)\rceil.

If a minimum separator QQ has size ℓ<q\ell< q, form AQA_Q and set b=r−ℓb = r-\ell. The parity lemma, with rr in place of kk, gives

y(AQ)≥b,b>εℓ,ℓ≥1(32)y(A_Q) \ge b,\qquad b > \varepsilon\ell,\qquad\ell\ge1 \tag*{(32)}

for every fixed full-requirement comparator yy. The middle inequality follows from ℓ≤q−1<r/(1+ε)\ell\le q-1 < r/(1+\varepsilon).

After each call, recompute a minimum cut and continue until the current target is met. There is no deterministic 1/a∗1/a_* cap in this version; the varying row threshold provides the needed growth bound. At most mm row procedures occur because each selects a new chord.

One comparator for all residual thresholds

Fix a prefix and its feasible cut vector yy. Let k=max⁡j≤irj≤mk = \max_{j\le i} r_j \le m; this is an analysis parameter, not an input to the algorithm. Put

WT(y)=∑e∉Tdeye,X=∑e∉Tdewe,B∗=54ln⁡(1+32mk).W_T(y) = \sum_{e\notin T} d_e y_e,\qquad X = \sum_{e\notin T} d_e w_e,\qquad B_* = \frac{5}{4}\ln\left(1+\frac{3}{2}mk\right).

An updated coordinate has pre-update value below b≤kb \le k; since γ/de≤1/4\gamma/d_e \le1/4, it always remains at most 3k/23k/2. For t=γ/det = \gamma/d_e,

1+mwenew=(1+t)(1+mwe)+t(b−1)≥(1+t)(1+mwe).1 + mw_e^{\mathrm{new}} = (1+t)(1+mw_e) + t(b-1) \ge(1+t)(1+mw_e).

The same logarithmic calculation as in (16) gives

∑j:e∈Ajγj≤B∗de.\sum_{j:e\in A_j} \gamma_j \le B_*d_e.

The increase in fractional cost at update jj is less than 2bjγj2b_j\gamma_j. Using y(Aj)≥bjy(A_j) \ge b_j, we obtain

X≤2∑jbjγj≤2∑eye∑j:e∈Ajγj≤2B∗WT(y).(33)X \le2\sum_j b_j\gamma_j \le2\sum_e y_e\sum_{j:e\in A_j}\gamma_j \le2B_*W_T(y). \tag*{(33)}

The dyadic coin rule satisfies πe≤2a∗Δe\pi_e \le2a_*\Delta_e and 1−πe≤e−a∗Δe1-\pi_e \le e^{-a_*\Delta_e}, including when a∗Δe≥1a_*\Delta_e \ge1. Hence expected sampled price is at most 4a∗B∗WT(y)4a_*B_*W_T(y).

A repair bound stratified by separator size

Fix a formal edge set QQ of size ℓ≥1\ell\ge1, and its row AQA_Q, whether or not that row is ever exposed. The process

MQ=1[I∩AQ=∅]exp⁡(a∗w(AQ))M_Q = 1[I \cap A_Q = \varnothing]\exp(a_*w(A_Q))

is a nonnegative supermartingale. If the row remains unhit, fresh coins give survival probability at most exp⁡(−a∗∑e∈AQΔe)\exp(-a_*\sum_{e\in A_Q}\Delta_e), canceling fractional growth; a purchase in the row makes the process zero forever.

A forced repair of this row occurs only after its mass reaches b>εℓb > \varepsilon\ell. Its probability is therefore at most e−a∗εℓe^{-a_*\varepsilon\ell}, by the same maximal inequality used in § 4. There are at most mℓm^\ell formal edge sets of size ℓ\ell. Choosing a∗ε≥2ln⁡(4m)a_*\varepsilon\ge2\ln(4m) gives

P(some forced repair∣T)≤∑ℓ=1mmℓe−a∗εℓ≤∑ℓ=1∞(16m)−ℓ=116m−1≤12m.(34)\mathbb{P}(\text{some forced repair}\mid T) \le\sum_{\ell=1}^{m}m^\ell e^{-a_*\varepsilon\ell} \le\sum_{\ell=1}^{\infty}(16m)^{-\ell} = \frac{1}{16m-1} \le\frac{1}{2m}. \tag*{(34)}

This sum does not enumerate rows in the algorithm. It is a probability estimate over the fixed implicit family.

By (32), a cheapest row cycle costs at most WT(y)/b≤WT(y)W_T(y)/b \le W_T(y). There are at most mm repairs, so their expected price is at most WT(y)/2W_T(y)/2. Altogether the conditional expected cycle price is at most

(4a∗B∗+1/2)WT(y).(35)(4a_*B_* + 1/2)W_T(y). \tag*{(35)}

Each tree edge in the union of requested paths defines a cut with comparator capacity at least one. Thus its union costs at most ∑eyedT(e)\sum_e y_e d_T(e). Averaging over the tree gives

E[c(Hi)]≤[D(n)+(1+D(n))(4a∗B∗+1/2)]c⊤y.(36)\mathbb{E}[c(H_i)] \le[D(n) + (1+D(n))(4a_*B_* + 1/2)]c^\top y. \tag*{(36)}

The parameter estimates in Section 9 finish the proof of Theorem 1.3.

Implementation and running time

Let PP be the number of requests processed. All algorithms use ordinary minimum-cut computations in the currently bought unit-capacity graph. Fix deterministic tie breaking for cuts and minimum-price objects; their particular choices do not affect the proof. Computing a parity row takes one traversal of TT and one scan of EE. An actual-cut row takes one edge scan. Cycle prices are computed once; the algorithms never change those prices to reflect earlier purchases.

Let MC⁡(n,m)\operatorname{MC}(n,m) be the running time of any polynomial-time minimum-cut routine for one pair. The uniform algorithms make O(P+R)O(P+R) such calls, where R=RTR=R_T or R0R_0. They perform O(Rlog⁡(m+1))O(R\log(m+1)) fractional updates, each scanning at most mm objects. Expanding the paths of all selected cycles takes at most O(mn)O(mn) additional work by a direct implementation; requested tree paths take at most O(Pn)O(Pn). These bounds give, after tree preprocessing where applicable,

O((P+R)MC⁡(n,m)+mRlog⁡(m+1)+mn+Pn)(37)O\bigl((P+R)\operatorname{MC}(n,m)+mR\log(m+1)+mn+Pn\bigr) \tag*{(37)}

arithmetic and graph operations. The direct-cut algorithm omits the path-expansion work. Sorting parallel bundles for Lemma 6.1 takes O(mlog⁡(m+1))O(m\log(m+1)) comparisons.

For a nonuniform row, a cheapest member satisfies

we0new+b/m=(5/4)(we0+b/m).w_{e_0}^{\mathrm{new}}+b/m=(5/4)(w_{e_0}+b/m).

It reaches mass bb within ⌈log⁡5/4(m+1)⌉\left\lceil\log_{5/4}(m+1)\right\rceil updates unless a purchase ends the row earlier. Thus the nonuniform algorithm has the same bounds with R=mR=m. In particular, no loop has length proportional to 1/ε1/\varepsilon or to an unknown maximum requirement.

The algorithms require no real-exponential sampling. A coin of probability 2−h2^{-h} is implemented by testing whether hh fair bits are all zero. The integer amplification parameters below are obtained by binomial recurrences, integer powers, and comparisons. All costs and updates are rational. Each update multiplies or adds rational quantities determined by input prices and the displayed parameters; over the polynomially many updates, their representations remain polynomial in the input length. Consequently the algorithms have polynomial running time with exact rational arithmetic and fair random bits, as well as the explicit operation bounds above.

Choosing the parameters

We now set all amplification constants and verify the inequalities used in the analysis. Natural logarithms are denoted by ln⁡\ln; changing bases in asymptotic expressions affects only constants. The case m=1m=1 is served by its only edge when requested, so assume m≥2m\ge2.

Uniform parity cover

For q≥2q\ge2, let RT,NTR_T,N_T be given by (22) and (24), and set

gT=⌊log⁡2(2RTNT)⌋,aT=2(q+gT),ηT=min⁡{1,m/aT}.(38)g_T=\left\lfloor\log_2(2R_TN_T)\right\rfloor,\qquad a_T=2(q+g_T),\qquad\eta_T=\min\{1,m/a_T\}. \tag*{(38)}

Since β>1/2\beta>1/2,

βaT−q+1>gT≥ln⁡(2RTNT).\beta a_T-q+1>g_T\ge\ln(2R_TN_T).

This verifies (11). Also aT≥2qa_T\ge2q. For t≤(n−1)/2t\le(n-1)/2, the binomial estimate ∑j=0t(n−1j)≤(e(n−1)/t)t\sum_{j=0}^{t}\binom{n-1}{j}\le(e(n-1)/t)^t gives the needed entropy bound. For larger tt, use NT<2n−1N_T<2^{n-1}. Together these imply

ln⁡NT=O(qlog⁡(2+nq)).\ln N_T=O\left(q\log\left(2+\frac{n}{q}\right)\right).

Furthermore RT≤(q−1)(n−1)R_T \le(q-1)(n-1), and hence log⁡(2RT)=O(log⁡(q+1)+log⁡(n+1))\log(2R_T)=O(\log(q+1)+\log(n+1)). Both terms are O(qlog⁡(2+n/q))O(q\log(2+n/q)): the first is O(q)O(q), and t↦tlog⁡(2+n/t)t\mapsto t\log(2+n/t) is increasing on t>0t>0. Consequently

aT=O(qlog⁡(2+nq)),B(aT)=O(log⁡(1+mq)).(39)a_T=O\left(q\log\left(2+\frac{n}{q}\right)\right),\qquad B(a_T)=O\left(\log\left(1+\frac{m}{q}\right)\right). \tag*{(39)}

The additive 1/21/2 in (28) is absorbed by aTB(aT)a_TB(a_T): here aT≤6ma_T\le6m, and aTln⁡(1+3m/(2aT))a_T\ln(1+3m/(2a_T)) is bounded below by a positive constant. Using q≤2(q−1)q\le2(q-1) proves (4).

For the running-time condition, NT<2n−1N_T<2^{n-1}, RT≤mR_T\le m, q≤mq\le m, and n−1≤mn-1\le m imply

aT≤2(q+n−1+⌈log⁡2(2m)⌉)≤6m.a_T\le2\left(q+n-1+\lceil\log_2(2m)\rceil\right)\le6m.

Thus ηT≥1/6\eta_T\ge1/6, as required for (19). The binomial sums have polynomial-size integer representations and are computed without enumerating their subsets.

Uniform direct cuts

For 1≤q≤k1\le q\le k, set

N0=2n−1,R0=min⁡{m,q(n−1)},g0=⌈log⁡2(2R0N0)⌉,a0=2(q+g0).(40)N_0=2^{n-1},\qquad R_0=\min\{m,q(n-1)\},\qquad g_0=\lceil\log_2(2R_0N_0)\rceil,\qquad a_0=2(q+g_0). \tag*{(40)}

Again βa0−q+1>g0≥ln⁡(2R0N0)\beta a_0-q+1>g_0\ge\ln(2R_0N_0), proving (12). The identity g0=n−1+⌈log⁡2(2R0)⌉g_0=n-1+\lceil\log_2(2R_0)\rceil and the bound R0≤q(n−1)R_0\le q(n-1) give

a0=Θ(n+q),a0≤6m,η0≥1/6.a_0=\Theta(n+q),\qquad a_0\le6m,\qquad\eta_0\ge1/6.

Substituting these estimates in (31) proves (5). This completes Theorem 1.2.

The near-exact target and the best of the two algorithms

Let q=⌈k/(1+ε)⌉q=\lceil k/(1+\varepsilon)\rceil. The ceiling is useful:

q−1<k1+ε,σ=k−q+1>εk1+ε,q−1σ<1ε.(41)q-1<\frac{k}{1+\varepsilon},\qquad\sigma=k-q+1>\frac{\varepsilon k}{1+\varepsilon},\qquad\frac{q-1}{\sigma}<\frac{1}{\varepsilon}. \tag*{(41)}

For every q≥1q\ge1, also k/2≤q≤kk/2\le q\le k and q/σ≤2/εq/\sigma\le2/\varepsilon. Therefore the parity guarantee is

O(D(n)[1k+1εlog⁡(2+nk)log⁡(1+mk)])LP⁡k(i),(42)O\left(D(n)\left[\frac{1}{k}+\frac{1}{\varepsilon}\log\left(2+\frac{n}{k}\right)\log\left(1+\frac{m}{k}\right)\right]\right)\operatorname{LP}_k(i), \tag*{(42)}

and the direct guarantee is

O(1ε(1+nk)log⁡(1+mn+k))LP⁡k(i).(43)O\left(\frac{1}{\varepsilon}\left(1+\frac{n}{k}\right)\log\left(1+\frac{m}{n+k}\right)\right)\operatorname{LP}_k(i). \tag*{(43)}

For q=1q=1, the tree-path guarantee is already at least as strong as the asserted asymptotic parity bound.

Apply Lemma 6.1 before choosing an algorithm. Both logarithms involving mm in Equations (42) and (43) are then O(log⁡(n+1))O(\log(n+1)), because m′≤k(n2)m'\le k\binom{n}{2}. The backbone term in (42) is absorbed. Choosing the algorithm with the smaller of these known upper bounds and substituting D(n)=O(log⁡(n+1))D(n)=O(\log(n+1)) from [3] proves Theorem 1.1. More concretely, use a declared rational upper bound D^=O(log⁡(n+1))\widehat{D}=O(\log(n+1)) on the sampler’s stretch. For q≥2q\ge2, replace B(a)B(a) in Equations (28) and (31) by the rational bound

B+(a)=54⌈log⁡2(1+3m′2a)⌉,B^{+}(a)=\frac{5}{4}\left\lceil\log_{2}\left(1+\frac{3m'}{2a}\right)\right\rceil,

and compare the two resulting coefficients, using D^\widehat{D} in place of D(n)D(n). These replacements change each bound by at most an absolute constant for the chosen parameters. Choose the smaller coefficient; for q=1q=1, use tree paths. The comparison uses integer arithmetic and no information about the arrival sequence.

For example, if k≥n/[log⁡(n+3)]Ck\ge n/[\log(n+3)]^{C} for fixed CC, the competitive ratio of the parity-cover algorithm, apart from the factor D(n)/εD(n)/\varepsilon, is at most OC(log⁡(n+1)[1+log⁡log⁡(n+3)])O_{C}(\log(n+1)[1+\log\log(n+3)]). If k=Ω(n)k=\Omega(n), the competitive ratio of the direct-cut algorithm is O(ε−1log⁡(n+1))O(\varepsilon^{-1}\log(n+1)). These parameter improvements do not reduce the worst-case logarithmic exponent uniformly over all kk.

Nonuniform requests

Take

a∗=⌈2ε⌈log⁡2(4m)⌉⌉.(44)a_{*}=\left\lceil\frac{2}{\varepsilon}\left\lceil\log_{2}(4m)\right\rceil\right\rceil. \tag*{(44)}

Then a∗ε≥2ln⁡(4m)a_{*}\varepsilon\ge2\ln(4m), the condition used in (34), and a∗=O(ε−1log⁡(m+1))a_{*}=O(\varepsilon^{-1}\log(m+1)). Feasibility gives k≤mk\le m, so B∗=O(log⁡(m+1))B_{*}=O(\log(m+1)). Substitution in (36), together with D(n)=O(log⁡(n+1))D(n)=O(\log(n+1)) from [3], proves (6). The algorithm uses only mm and ε\varepsilon in this choice, not kk.

The remaining exact-connectivity question

The positive results above isolate the role of slack. A deficient separator of size ℓ\ell has k−ℓk-\ell certified comparator witnesses. At exact connectivity, a final separator can have ℓ=k−1\ell=k-1, so this guarantee supplies only one witness. Our proof then loses its discount while the family of possible separators can still be large. No general exact o(k)o(k) polylog nn bound follows from the analysis.

The logarithmic lower bound already known at small fixed connectivity [1] does not imply that polynomial dependence on kk is necessary. In particular, a construction with competitive ratio Ω(h)\Omega(h) on n=Θ(k2h)n=\Theta(k2^{h}) vertices remains a logarithmic-size lower bound even after writing h=kαh=k^{\alpha}. We make no universal lower-bound claim polynomial in kk.

There is nevertheless a concrete obstruction to a natural completion argument. Appendix § 13 gives a simple graph with one request, n=Θ(klog⁡k)n=\Theta(k\log k), and equal fractional and integral augmentation optima. Independently rounding one optimum fractional solution needs amplification Ω(k)\Omega(k) for constant success probability; smaller amplification can leave a constant fraction of the optimum to be paid in repairs. This rules out that particular independent-rounding estimate. A successful exact-completion algorithm could instead exploit correlations, adaptivity, or a different fractional representation.

AI Use Statement

This work resulted from extensive interaction between the authors and OpenAI Astra, with the authors providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the authors, with Gemini Argon assisting in some parts. The authors directed the process and evaluated the proposed ideas and arguments. Lean files formalizing the main theorem are available on GitHub at https://github.com/hajiaghayi/Online-Survivable-Network.

Constructing a spanning-tree distribution from average stretch

This appendix records a polynomial-time route to the older published stretch bound. The headline results instead use the sharper logarithmic theorem of [3]. It also explains why an average-stretch statement suffices for the per-edge expectation in (2). The reduction uses the spanning-tree game of [4] and the average-stretch algorithm of [5].

First assume a simple graph with positive rational edge lengths. Write sT(e)=dT(e)/ces_T(e)=d_T(e)/c_e, and let Γ=O(log⁡(n+1)log⁡log⁡(n+3))\Gamma=O(\log(n+1)\log\log(n+3)) be an integer upper bound for the average-stretch guarantee on graphs with O(n2)O(n^2) vertices. For a rational distribution pp on the mm edges, replace edge ee by μe=1+⌊mpe⌋\mu_e=1+\lfloor mp_e\rfloor parallel copies of the same length. Their total number MM is at most 2m2m, and μe≥mpe\mu_e\ge mp_e. An average-stretch tree on this replicated graph therefore gives

∑epesT(e)≤1m∑eμesT(e)≤2Γ.(45)\sum_e p_e s_T(e) \le\frac{1}{m}\sum_e \mu_e s_T(e) \le2\Gamma. \tag*{(45)}

To use an average-stretch algorithm stated for simple graphs, subdivide each copy into two half-length edges. There are n+M=O(n2)n+M=O(n^2) vertices. In a spanning tree of the subdivision, each new vertex is either a leaf or has both incident edges present. The copies with both halves present project to a spanning tree on the original vertices. For a projected tree copy, the two half-edge stretches sum to 22; for another copy, they sum to 2+2sT(e)2+2s_T(e). In both cases the sum is at least 2sT(e)2s_T(e). Hence the average-stretch guarantee on the subdivision implies the inequality used in (45).

We convert this response oracle into a small explicit distribution by multiplicative weights. Start with w1(e)=1w_1(e)=1. At iteration tt, form

pt(e)=wt(e)∑fwt(f),pt′(e)=12pt(e)+12m,p_t(e)=\frac{w_t(e)}{\sum_f w_t(f)}, \qquad p'_t(e)=\frac{1}{2}p_t(e)+\frac{1}{2m},

and obtain a response tree TtT_t from (45) for pt′p'_t. It satisfies

∑ept(e)sTt(e)≤4Γ,sTt(e)≤4mΓfor all e.\sum_e p_t(e)s_{T_t}(e)\le4\Gamma, \qquad s_{T_t}(e)\le4m\Gamma\quad\text{for all }e.

Put ht(e)=sTt(e)/(4mΓ)∈[0,1]h_t(e)=s_{T_t}(e)/(4m\Gamma)\in[0,1] and update wt+1(e)=wt(e)(1+ht(e)/2)w_{t+1}(e)=w_t(e)(1+h_t(e)/2). If Wt=∑ewt(e)W_t=\sum_e w_t(e), then

ln⁡WL+1≤ln⁡m+L2m,38∑t=1Lht(e)≤ln⁡wL+1(e)≤ln⁡WL+1.\ln W_{L+1}\le\ln m+\frac{L}{2m},\qquad\frac{3}{8}\sum_{t=1}^{L}h_t(e)\le\ln w_{L+1}(e)\le\ln W_{L+1}.

The second inequality uses ln⁡(1+x/2)≥3x/8\ln(1+x/2)\ge3x/8 on [0,1][0,1]. Choose a power of two LL with

2m⌈log⁡2(m+1)⌉≤L<4m⌈log⁡2(m+1)⌉.2m\left\lceil\log_2(m+1)\right\rceil\le L<4m\left\lceil\log_2(m+1)\right\rceil.

Since L≥2mln⁡mL\ge2m\ln m, the uniform distribution over the LL response trees has

max⁡e1L∑t=1LsTt(e)≤323Γ.\max_e\frac{1}{L}\sum_{t=1}^{L}s_{T_t}(e)\le\frac{32}{3}\Gamma.

This is (2). The construction makes O(mlog⁡(m+1))O(m\log(m+1)) polynomial-time average-stretch calls and uses polynomial-time rational arithmetic. A tree is sampled by log⁡2L\log_2 L fair bits.

For a multigraph, retain one cheapest edge per endpoint pair only for tree selection. Its expected-distance bound also applies to every other edge in that bundle, because its cost is no smaller. All original edges remain in the connectivity instance, unless the separate benchmark-preserving reduction of Lemma 6.1 is explicitly used. Zero costs are treated as in Section 3.

A limitation of independent rounding for exact completion

The slack in our connectivity guarantee is essential to the present rounding analysis. The following example explains why exact completion requires more than independent sampling of a feasible fractional augmentation. It concerns one rounding rule on a fixed fractional solution, rather than a lower bound against online algorithms: there is only one request, and its minimum-cost integral augmentation is easy to find.

Proposition B.1. For integers N≥3N\ge3 and L≥2L\ge2, there is a simple undirected graph with

n=N(2L−1)+2,m=3NL,k=N+1,n=N(2L-1)+2,\qquad m=3NL,\qquad k=N+1,

and a free base of ss–tt connectivity NN, such that the capacitated cut-LP optimum and the integral augmentation optimum both equal LL. There is an optimal fractional solution yy with the following property. If paid edges are selected independently, each with probability at most ρye\rho y_e, where 0≤ρ≤N0\le\rho\le N, then

P[λ(s,t)≥k]≤N(ρ/N)L.(46)\mathbb{P}[\lambda(s,t)\ge k]\le N(\rho/N)^L. \tag*{(46)}

In particular, for L=⌈ln⁡N⌉L=\lceil\ln N\rceil, success probability at least a fixed p0∈(0,1]p_0\in(0,1] requires ρ≥(p0/e)N=Ω(k)\rho\ge(p_0/e)N=\Omega(k). Moreover, if ρ≤N/4\rho\le N/4 and L≥48ln⁡NL\ge48\ln N, the minimum additional cost needed to attain connectivity kk is at least L/2L/2 with probability at least 1−N−31-N^{-3}. Both conclusions apply to families with n=Θ(klog⁡k)n=\Theta(k\log k).

Proof. Take NN internally vertex-disjoint ss–tt paths, each consisting of LL free edges. For every path edge uvuv, introduce a private vertex zuvz_{uv} and the detour uzuvvuz_{uv}v, where uzuvuz_{uv} is free and zuvvz_{uv}v costs one. All free edges are acquired initially. The graph is simple, and counting its path interiors and detour vertices gives the stated size.

Figure 3. A three-stage channel. Solid edges are free; each dashed edge costs one. The construction has NN channels, each with LL stages, sharing only ss and tt. A channel contributes its second unit of connectivity only after every paid edge on that channel is purchased.

The fractional and integral optima. Set ye=1y_e = 1 on free edges and ye=1/Ny_e = 1/N on paid edges. Each ss–tt cut crosses an original path edge on every channel. The corresponding detour also crosses that cut and contributes at least 1/N1/N of fractional capacity, regardless of the shore containing its private vertex. Thus every such cut has yy-capacity at least N+1N + 1. The fractional cost is NL/N=LNL/N = L.

For the reverse inequality, consider the LL layer cuts: the iith cut places every path vertex at depths 0,…,i−10,\ldots,i-1 on the ss side and those at depths i,…,Li,\ldots,L on the tt side, with each detour vertex on the same side as its preceding path vertex. Its boundary contains exactly NN free edges and the NN paid edges of stage ii. Since each free-edge variable is at most one, every feasible solution of the capacitated cut LP assigns total paid capacity at least one to each layer. The layers use disjoint sets of paid edges, so their constraints imply LP≥L\mathrm{LP} \ge L. Completing all detours on one channel costs LL and supplies one additional unit of connectivity. Hence both optima equal LL.

Why independent sampling fails. Each stage of a channel has capacity one until its paid detour edge is purchased, when its capacity becomes two. Since these stages are in series, the channel has connectivity two exactly when all its paid edges have been purchased; otherwise it has connectivity one. Different channels share only their endpoints. Consequently the total connectivity is exactly NN plus the number of completed channels. Independence bounds the probability of completing any particular channel by (ρ/N)L(\rho/N)^L; a union bound proves (46). If L=⌈ln⁡N⌉L = \lceil\ln N\rceil and the success probability is at least p0∈(0,1]p_0 \in(0,1], then

ρ≥N(p0/N)1/L≥(p0/e)N.\rho\ge N(p_0/N)^{1/L} \ge(p_0/e)N.

using L≥ln⁡NL \ge\ln N and p01/L≥p0p_0^{1/L} \ge p_0.

The cost of repairing the sample. Let XjX_j be the number of paid edges selected on channel jj. The minimum repair cost is exactly L−max⁡jXjL - \max_j X_j, since attaining connectivity N+1N + 1 requires completing at least one channel. For ρ≤N/4\rho\le N/4, each XjX_j is stochastically dominated by Bin⁡(L,1/4)\operatorname{Bin}(L,1/4). A Chernoff bound and a union bound give

P[max⁡jXj≥L/2]≤Ne−L/12≤N−3(L≥48ln⁡N).\mathbb{P}\left[\max_j X_j \ge L/2\right] \le N e^{-L/12} \le N^{-3} \qquad(L \ge48\ln N).

On the complementary event, every channel needs at least L/2L/2 additional paid edges, proving the repair claim. Taking L=⌈ln⁡N⌉L = \lceil\ln N\rceil for the first conclusion, or L=⌈48ln⁡N⌉L = \lceil48\ln N\rceil for the second, gives n=Θ(klog⁡k)n = \Theta(k\log k).

In particular, for ρ=N\rho= \sqrt{N} and L=⌈48ln⁡N⌉L = \lceil48\ln N\rceil, the expected repair cost is at least (1−N−3)LP/2(1-N^{-3})\mathrm{LP}/2 for all sufficiently large NN. Thus no universal bound of the form E[repair cost]≤Ce−cρLP\mathbb{E}[\text{repair cost}] \le C e^{-c\rho}\mathrm{LP}, with fixed C,c>0C,c > 0, holds for this rounding procedure. The same example applies to independent fundamental-cycle sampling when the spanning tree lies in the free base: selecting a paid fundamental cycle adds exactly its single paid edge. The example leaves open methods that correlate purchases, adapt to failed cuts, or choose a different fractional augmentation.

References

  1. [1]Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and stochastic survivable network design. SIAM Journal on Computing, 41(6):1649–1672, 2012. doi: 10.1137/09076725X. URL https://www.contrib.andrew.cmu.edu/~ravi/sicomp12.pdf. Preliminary version in STOC 2009.DOI
  2. [2]Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Greedy algorithms for online survivable network design. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of Leibniz International Proceedings in Informatics, pages 152:1–152:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.ICALP.2018.152.DOI
  3. [3]Mohammad Hajiaghayi. Logarithmic embeddings into probabilistic spanning trees for distances and capacities, 2026. URL https://arxiv.org/abs/2611.05189. arXiv:2611.05189.
  4. [4]Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78–100, 1995. doi: 10.1137/S0097539792224474. URL https://dwest.web.illinois.edu/pubs/kserver.pdf.DOI
  5. [5]Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. SIAM Journal on Computing, 48(2):227–248, 2019. doi: 10.1137/17M1115575. Preliminary version in STOC 2012.DOI
  6. [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.DOI
  7. [7]Piotr Berman and Chris Coulston. On-line algorithms for Steiner tree problems (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pages 344–353. ACM, 1997. doi: 10.1145/258533.258618.DOI
  8. [8]Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. doi: 10.1007/s004930170004.DOI
  9. [9]Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson. Tight bounds for online weighted tree augmentation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of Leibniz International Proceedings in Informatics, pages 88:1–88:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPIcs.ICALP.2019.88.DOI
  10. [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.DOI
  11. [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.DOI
  12. [12]Sander Borst, Marek Eliáš, and Moritz Venzin. Stronger adversaries grow cheaper forests: Online node-weighted Steiner problems. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 3842–3864. SIAM, 2025. doi: 10.1137/1.9781611978322.129. URL https://arxiv.org/abs/2410.18542.
  13. [13]Mohit Garg and Aditya Subramanian. Online connectivity augmentation. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 85–104. SIAM, 2026. doi: 10.1137/1.9781611978971.4.DOI
  14. [14]Mohit Garg, Felix Hommelsheim, and Alexander Lindermayr. Optimal online weighted connectivity augmentation, 2026. URL https://arxiv.org/abs/2610.42046. arXiv:2610.42046.
  15. [15]Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, and Michael Zlatín. Weighted and unweighted online connectivity augmentation via geometric hitting set, 2026. URL https://arxiv.org/abs/2611.08570. arXiv:2611.08570.
  16. [16]Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary 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.DOI

Paper details

vlnc:W_8wm5p5pt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI Astra, Gemini Argon

View statement
Looking for related papers…
Contents