betaFeedback

WorksComputer Science

Metric Facility Location under Batched Random Order

Abstract

We study online metric facility location in the batched random-order model. An adversary partitions nn clients into BB nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is Θ ⁣(min⁡{log⁡(B+1),log⁡(n−B+2)}). Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a Θ(log⁡n)Θ(\sqrt{\log n}) ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know nn nor BB. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

Introduction

Online metric facility location, introduced by Meyerson [17], is a cornerstone of online algorithms and has attracted sustained interest [5, 12, 11, 10]. Clients v1,…,vnv_1,\ldots,v_n from an underlying metric space (X,d)(X,d) arrive one by one, and each must be irrevocably assigned to an open facility upon arrival. Opening a facility at a permitted location yy costs f(y)f(y), and assigning a client to it costs their distance. The objective is to minimize the total opening and connection cost. Every client location is a permitted facility location. Opening costs are uniform if f(y)=ff(y)=f everywhere, and nonuniform otherwise. In the uniform case, our algorithm opens facilities only at arriving clients. In the nonuniform case, the permitted locations, their metric, and their opening costs are known in advance.

The arrival order strongly affects the achievable guarantees. A uniformly random permutation of the clients permits constant competitive ratios for both opening-cost models [17], whereas adversarial order already requires Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) for uniform costs [5]. These assumptions describe two extremes: adversarial analysis protects against every possible arrival sequence, while random order assumes that all client permutations are equally likely. Neither directly captures requests that arrive together because they share a source or arise from the same event.

We study the batched random-order model, introduced for set cover by Gupta et al. [6]. An oblivious adversary fixes the nn clients and partitions them into BB nonempty batches, which arrive in uniformly random order. We remark that different batches might have different sizes. Each batch is revealed in full, and all its clients must be served before the next batch arrives.

This captures requests that arrive together because they share a source or arise from the same event, while retaining randomness in the order of these groups. For example, clients from one region may arrive together, so an early batch need not represent the full instance. Even after seeing that entire batch, the algorithm must serve it without knowing the demand in other regions.

Two immediate upper bounds do not use the random batch order. Solving each batch independently to within a constant factor gives an O(B)O(B)-competitive algorithm, since the optimum for any one batch costs at most the optimum for the full instance. Alternatively, ignoring batch boundaries gives Meyerson’s O(log⁡n)O(\log n) guarantee [17], and, as mentioned, Fotakis [5] sharpened the latter to the optimal Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) ratio for adversarial arrival order. Moreover, revealing whole batches does not by itself permit a sublinear dependence on BB: the lower bound construction of [5] forces an Ω(B)\Omega(B) lower bound when the BB phases are revealed as batches of colocated clients. Our question is how much the random order of the batches helps: we improve the dependence on BB from linear to logarithmic, and the bound in terms of nn from O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) to O(log⁡n)O(\sqrt{\log n}).

Our results and techniques

Our main result determines the optimal competitive ratio in the batched random-order model, with a tight dependence on both the number of batches BB and the number of excess clients n−Bn-B.

Theorem (Informal version of Theorems 3.1, 4.1 and 5.3). For nn clients in BB nonempty batches, the optimal randomized competitive ratio, for both uniform and arbitrary known positive opening costs, is

Θ(min⁡{log⁡(B+1),log⁡(n−B+2)}).\Theta\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right).

In particular, the ratio is constant both when all clients arrive together and when every batch is a singleton. For B=Θ(nα)B = \Theta(n^{\alpha}) with fixed 0<α<10 < \alpha< 1, it is instead Θ(log⁡n)\Theta(\sqrt{\log n}).

Our algorithms shuffle uniformly at random each batch and process its clients one at a time, although the model allows joint decisions for the entire batch (Figure 1). Nonetheless, we obtain optimal asymptotic competitive ratios, which we found intriguing. We next describe the details of the algorithms for the uniform and non-uniform case.

Illustration of the batched random-order model and client shuffling

Figure 1. The adversary fixes the clients and their batches, which are then uniformly permuted. Each batch is revealed in full, but our algorithms additionally shuffle its clients, as illustrated for batch b3b_3.

Uniform costs. We describe our results for the uniform opening cost case first.

The algorithm. We use Meyerson’s algorithm [17]: when client vv is processed, it opens a facility at vv with probability min⁡{1,d(v,Fv)/f}\min\{1, d(v,F_v)/f\}, where FvF_v is the set of facilities already open, ff is their common opening cost, and d(v,Fv)d(v,F_v) the distance of vv to its nearest facility in FvF_v. Otherwise, we connect vv to its nearest open facility. Equivalently, for each client we draw an independent Uv∼Unif⁡(0,1)U_v \sim\operatorname{Unif}(0,1) and open at vv if fUv≤d(v,Fv)fU_v \le d(v,F_v). Following Meyerson, we describe the rule when clients can themselves host facilities. If clients and permitted facility sites are disjoint, we first map each client to its nearest permitted site, which changes only the constant in the connection-cost bound (Observation 2.1), following Meyerson [17].

We analyze one optimal cluster CC at a time, writing cc for its facility and conn⁡(C)=∑v∈Cd(c,v)\operatorname{conn}(C) = \sum_{v \in C} d(c,v). Following the balanced-opening analysis of Huang and Jiang [10], we identify a sufficient condition for an opening to bring a facility closer to cc; we call such openings certified. Their expected number controls the algorithm’s cost, up to an additive O(conn⁡(C))O(\operatorname{conn}(C)) (Lemma 3.2). Within a batch, the first certified client is biased towards clients closer to cc and, therefore, its opening lets us charge all later certifications in that batch to its clients’ connection cost (Lemma 3.3). If KCK_C counts batches containing a certification from CC, these two steps give

E[ALG⁡(C)]≤O(conn⁡(C))+O(f)E[KC],\mathbb{E}[\operatorname{ALG}(C)] \le O(\operatorname{conn}(C)) + O(f)\mathbb{E}[K_C],

where ALG⁡(C)\operatorname{ALG}(C) is the cost paid by our algorithm on cluster CC. Thus we need only to bound the number of batches that pay for a first certification.

The logarithmic bound in BB. For this purpose, we use the algorithm’s independent uniform variables Uv∈(0,1)U_v \in(0,1) to assign the static keys Zv=d(c,v)+fUvZ_v = d(c,v) + fU_v. After processing vv, the distance to cc, capped at ff, is strictly below ZvZ_v. Consequently, a batch containing a certification must have a smaller minimum key than every preceding batch intersecting CC. Once the keys are fixed, the batches still arrive in uniformly random order: the rrth batch has the smallest key seen so far with probability 1/r1/r. Summing gives E[KC]≤HB=O(log⁡(B+1))\mathbb{E}[K_C] \le H_B = O(\log(B+1)) (Lemma 3.5).

The square-root logarithmic bound in n−Bn-B. We obtain a second bound on the same count by measuring how much a certification decreases the distance to cc. Fix ρ>1\rho> 1. Starting from a distance capped at ff, there can be only O(log⁡n/log⁡ρ)O(\log n/\log\rho) decreases by a factor of ρ\rho before the capped distance falls below f/nf/n. After that, each remaining client is certified with probability at most 1/n1/n, contributing at most one further certification in expectation. Every other certification requires a small lottery value, namely fUv<(ρ−1)d(c,v)fU_v < (\rho- 1)d(c,v). The batches containing a client satisfying this condition are fixed by the lottery variables, independently of the batch order. Their expected number is at most (ρ−1)conn⁡(C)/f(\rho- 1)\operatorname{conn}(C)/f, and we can count records among these batches just as above. Together, the three cases give Lemma 3.6

E[KC]≤O(1+log⁡nlog⁡ρ+log⁡ρ)+conn⁡(C)f.\mathbb{E}[K_C] \le O\left(1+\frac{\log n}{\log\rho}+\log\rho\right)+\frac{\operatorname{conn}(C)}{f}.

where the last term is absorbed into the connection cost. Choosing log⁡ρ=max⁡{1,log⁡n}\log\rho=\max\{1,\sqrt{\log n}\} balances the other two terms and gives an O(log⁡n)O(\sqrt{\log n}) bound. To replace nn by n−Bn-B, we run separate copies on singleton and nonsingleton batches, each using its own facility set. The singleton clients arrive in ordinary random order, where the algorithm is constant competitive. The other copy receives at most ∑b:∣b∣≥2∣b∣≤2(n−B)\sum_{b:\lvert b\rvert\ge2}\lvert b\rvert\le2(n-B) clients, and its batches retain uniformly random relative order. We open the union of the two copies’ facilities, so the actual cost is at most the sum of their costs (Observation 2.2). The nonsingleton copy also retains the bound in BB, giving the minimum of the two guarantees for the combined algorithm.

Nonuniform costs. We round opening costs up to powers of two f1<⋯<fmf_1<\cdots<f_m and use a marginal version of Meyerson’s rule. Let MjM_j contain the facilities costing at most fjf_j after rounding. Before processing vv, put Δv(0)=d(v,Fv)\Delta_v^{(0)}=d(v,F_v) and Δv(j)=min⁡{d(v,Fv),d(v,Mj)}\Delta_v^{(j)}=\min\{d(v,F_v),d(v,M_j)\}. Independently at each level jj, we select a nearest facility in MjM_j for opening with probability

pv(j)=min⁡{1,Δv(j−1)−Δv(j)fj}.p_v^{(j)}=\min\left\{1,\frac{\Delta_v^{(j-1)}-\Delta_v^{(j)}}{f_j}\right\}.

All lotteries for a client vv use the same facility set FvF_v, open before vv is considered. We open the selected facilities and connect vv to its nearest available facility. Thus, each price level lottery pays for its marginal reduction in distance to the client, rather than the entire distance (Eq. (2)).

The main new difficulty lies in the analysis within a batch. At a single price level, certification need not favor clients nearer to cc, and analyzing the price levels separately could charge to the algorithm the optimal connection costs within a cluster repeatedly for each level. The key is to sum certification charges over all price levels before bounding connection costs in a way that consecutive marginal distances cancel. Within each batch, we distinguish between the half of clients closest to the optimal center and the half farthest from it. We then pair each client in the farther half with a distinct client in the nearer half. Either member of a pair arrives first with probability 1/21/2, which lets us bound their total expected charge by a constant times the nearer client’s charge (Claim 4.7).

This allows us to bound separately the marginal cost incurred at each price level by using the same arguments used for the proof of the uniform case (Proposition 4.9). We apply its record and progress bounds at each level and sum the resulting charges using the geometric prices, thus obtaining the same approximation bounds without introducing a factor for the number of levels (Theorem 4.1).

Matching lower bounds. We adapt Fotakis’s hidden-path tree construction [5] (Figure 2). The metric is a known binary tree of depth hh, with unit opening costs, but all clients lie on a uniformly chosen root-to-leaf path that is hidden from the algorithm. A newly revealed vertex deeper than all previous ones narrows the possible continuation of the path. The batch sizes ensure that serving a batch from outside its subtree costs at least one. Alternatively, facilities opened inside the current subtree may be left outside the next revealed subtree, and each such opening can be charged only once. Together, these charges give an expected cost proportional to the number of new deepest revelations (Lemma 5.1).

The lower-bound construction: a hidden path and batches placed along the path, with depth, number of batches, and clients per batch shown

Figure 2. The lower-bound construction, with m=2h+3m = 2^{h+3}. The blue path is chosen at random and hidden from the algorithm; the gray branches show other possible continuations. We place 2h−i2^{h-i} batches of mim^i clients at depth ii. Having more batches at shallower depths ensures that each depth is revealed before all deeper ones with probability at least 1/21/2. The edge entering a depth-ii subtree has length m−im^{-i}, so serving one of its batches entirely from outside that subtree costs at least mim−i=1m^i m^{-i} = 1. In contrast, the offline solution can serve all clients from a single facility at the final leaf for a total cost of O(1)O(1).

The obstacle is that with one batch per depth level, random order produces only Hh+1=O(log⁡h)H_{h+1} = O(\log h) new deepest revelations, rather than Θ(h)\Theta(h). We therefore place 2h−i2^{h-i} batches at depth ii. This depth is revealed before every deeper one with probability

2h−i∑ℓ=ih2h−ℓ=2h−i2h−i+1−1≥12,\frac{2^{h-i}}{\sum_{\ell=i}^{h} 2^{h-\ell}} = \frac{2^{h-i}}{2^{h-i+1}-1} \ge\frac{1}{2},

so the expected online cost is now Ω(h)\Omega(h). The number of batches is Bh=2h+1−1B_h = 2^{h+1}-1, explaining the logarithmic dependence on BB. To keep the offline cost small despite these repetitions, we shrink edge lengths by a factor m=2h+3m = 2^{h+3} at each depth. A batch at depth ii contains mim^i clients, and its parent edge has length m−im^{-i}. Opening just at the hidden leaf gives

OPT⁡≤1+∑i=0h−12h−imi∑ℓ=i+1hm−ℓ≤1+2h+1−2m−1<54.\operatorname{OPT} \le1 + \sum_{i=0}^{h-1} 2^{h-i}m^i \sum_{\ell=i+1}^{h} m^{-\ell} \le1 + \frac{2^{h+1}-2}{m-1} < \frac{5}{4}.

However, these large batches use nh=∑i=0h2h−imi=exp⁡(Θ(h2))n_h = \sum_{i=0}^{h} 2^{h-i}m^i = \exp(\Theta(h^2)) clients, and hence log⁡(nh−Bh)=Θ(h2)\log(n_h - B_h) = \Theta(h^2) (Lemma 5.2). Thus depth hh costs exponentially many batches in hh and exponentially many excess clients in h2h^2. Choosing the largest depth that fits both budgets yields the two terms in our lower bound. Finally, adding singleton batches and extra clients at the root gives every feasible pair (n,B)(n, B): one additional root facility serves all added clients without revealing more of the hidden path (Theorem 5.3).

Related work

Metric facility location. Offline metric facility location has been a testing ground for approximation techniques. Shmoys et al. [20] gave the first constant-factor approximation by rounding a linear-programming relaxation. Mahdian et al. [18] obtained a 1.52-approximation using cost scaling, greedy improvement, and dual fitting; Li [14] later obtained a 1.488-approximation by randomizing an LP-rounding parameter and combining the resulting algorithm with an earlier greedy algorithm. A related line of work seeks stronger guarantees that preserve the coefficient of the opening cost while approximating the connection cost. Cohen-Addad et al. [3] combined dual fitting and local search to obtain a Lagrangian-multiplier-preserving approximation strictly below 2, with consequences for kk-median. This guarantee is different from the usual approximation ratio for the total cost.

Metric facility location with general cost functions. Offline variants also connect facility location to network design and more general cost functions. Leonardi and Schäfer [16] studied cost sharing for connected facility location, where the open facilities must also be joined by a Steiner tree. They developed methods that recover a constant fraction of the solution cost while ensuring that a client’s charge cannot increase when more clients participate, including a primal-dual method with nonzero opening costs. For the related Steiner-tree problem, Byrka et al. [2] gave a (ln⁡4+ε)(\ln4 + \varepsilon)-approximation using iterative randomized rounding; Steiner-tree algorithms serve as building blocks in connected facility location. Abbasi et al. [1] considered submodular facility location, where a facility’s cost depends on its assigned set of clients through a monotone submodular function, and obtained an O(log⁡log⁡n)O(\log\log n)-approximation. These works address computation when all clients are known. Our bounds instead measure the cost of making irrevocable decisions before future batches are revealed.

Online metric facility location. Meyerson [17] introduced online facility location and proved constant competitiveness in random order for uniform and nonuniform opening costs. Fotakis [5] established the optimal adversarial ratio Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n). For uniform costs, Kaplan et al. [12] proved that Meyerson’s algorithm is exactly 4-competitive in random order and gave a 3-competitive modification. Recent work further improves the constants using arrival times: Huang and Jiang [10] obtain a ratio below 2.42 for uniform costs, while Peng and Tang [PT26] improve the nonuniform-cost bounds. Huang and Jiang also use the center-excess certification (d(c,F)−d(c,v))+(d(c,F)-d(c,v))_{+} that underlies our uniform analysis. Our contribution is its batchwise analysis through static keys and progress bounds, and the extensions to nonuniform costs.

Learning-augmented online metric facility location. Predictions offer another way to improve online facility location. Jiang et al. [11] augment the algorithm with predictions of the optimal facility serving each client and analyze the dependence on the maximum prediction error. For uniform costs, Fotakis et al. [4] obtain matching bounds in terms of the sum of prediction errors. Lattanzi et al. [LPS26] develop online rounding algorithms and applications to learning-augmented facility location. These works exploit advice about future requests or an optimal solution; our algorithms instead exploit the arrival distribution.

Algorithms in the random-order model. The random-order model has also been studied extensively for secretary, packing, and covering problems; Gupta and Singla [9] survey the principal techniques and their relation to other stochastic models. For facility location, Lang [13] studies an interpolation in which an adversary can buffer and reorder a bounded number of requests from an initially random stream. Kaplan et al. [12] also study partial adversarial orders. These models alter a random stream, whereas here a fixed partition or hierarchy determines which groups are permuted. For set cover with mm sets and nn elements, Gupta et al. [6] give an O(log⁡(mn))O(\log(mn))-competitive random-order algorithm, LearnOrCover. The same paper introduces batched random-order set cover: entire batches are revealed in a uniformly random order. For bb equal-size batches of ss elements, they prove a lower bound of Ω(log⁡blog⁡s)\Omega(\log b\log s) for polynomial-time randomized algorithms, unless NP⊆BPP\mathrm{NP} \subseteq\mathrm{BPP}. We depart slightly from their batch-revelation convention, as our algorithms do not need batches to be revealed in full, and the batches need not be of the same size. However, our lower bounds allow every use of the fully revealed batch which makes the problem only easier. Gupta et al. [7] extend the covering framework to nonmetric facility location and relate random-order algorithms to single-sample prophet algorithms. Gupta et al. [8] give a direct connection to stochastic mirror descent and online convex optimization, recovering the set-cover guarantee and extensions to other covering problems. In the metric setting considered here, the triangle inequality allows us to compare clients served by the same optimal facility and to measure how an opening helps future clients in that cluster.

Preliminaries

In the batched random-order metric facility location problem, an oblivious adversary partitions a multiset V={v1,…,vn}V = \{v_1,\ldots,v_n\} of nn clients into BB nonempty batches {b1,…,bB}\{b_1,\ldots,b_B\} not necessarily of equal size. Batches arrive in uniformly random order, and each batch is revealed in full and must be served before the next arrives. Our algorithms independently shuffle each batch and process its clients one at a time.

Notation. We write d(v,F)=min⁡y∈Fd(v,y)d(v,F)=\min_{y\in F}d(v,y), with d(v,∅)=∞d(v,\varnothing)=\infty, [x]+=max⁡{x,0}[x]_+=\max\{x,0\}, and Hs=∑i=1s1/iH_s=\sum_{i=1}^{s}1/i. Fixed an optimal solution with clusters C\mathcal{C}, for an optimal cluster CC served by facility cc, write Cb=C∩bC_b=C\cap b and conn⁡(S)=∑v∈Sd(c,v)\operatorname{conn}(S)=\sum_{v\in S}d(c,v) for S⊆CS\subseteq C. Thus, the offline optimal cost can be decomposed into the optimal connection cost and optimal opening cost: OPTconn=∑Cconn⁡(C)\mathrm{OPT}_{\mathrm{conn}}=\sum_C\operatorname{conn}(C), OPTopen=∑Cf(c)\mathrm{OPT}_{\mathrm{open}}=\sum_C f(c), and OPT=OPTconn+OPTopen\mathrm{OPT}=\mathrm{OPT}_{\mathrm{conn}}+\mathrm{OPT}_{\mathrm{open}}. Similarly, if we let cost⁡(v)\operatorname{cost}(v) be the cost incurred while processing vv, and ALG(C)=∑v∈Ccost⁡(v)\mathrm{ALG}(C)=\sum_{v\in C}\operatorname{cost}(v), then the total algorithm’s cost is ALG=∑CALG(C)\mathrm{ALG}=\sum_C\mathrm{ALG}(C). Finally, as it is customary, an algorithm is said to be α\alpha-competitive if E[ALG]≤αOPT\mathbb{E}[\mathrm{ALG}]\leq\alpha\mathrm{OPT}, where α≥1\alpha\geq1.

Clients and facility sites. As mentioned in § 1, for uniform costs, we follow Meyerson [17] in presenting the algorithm with openings at client locations.

Observation 2.1. Any bound aOPTconn+bOPTopena\mathrm{OPT}_{\mathrm{conn}}+b\mathrm{OPT}_{\mathrm{open}} valid against every fixed comparison solution when clients are permitted facility sites extends to

E[ALG]≤(2a+1)OPTconn+bOPTopen\mathbb{E}[\mathrm{ALG}] \leq(2a+1)\mathrm{OPT}_{\mathrm{conn}}+b\mathrm{OPT}_{\mathrm{open}}

for arbitrary client locations and known permitted sites. This holds for uniform and nonuniform costs, preserving nn, BB, and the arrival distribution.

Proof. Map each client vv to its nearest permitted site y(v)y(v), retaining its occurrence and batch, and run the algorithm with unchanged facility costs. For every comparison facility cc,

d(v,y(v))≤d(v,c),d(y(v),c)≤2d(v,c).d(v,y(v)) \le d(v,c), \qquad d(y(v),c) \le2d(v,c).

The original optimum therefore serves the projected clients with unchanged opening cost and at most twice its connection cost. Connecting each original client to the facility serving its projection adds at most ∑vd(v,y(v))≤OPTconn\sum_v d(v,y(v)) \le\mathrm{OPT}_{\mathrm{conn}}, proving the bound. □

Transferring bounds from nn to n−Bn-B. Our bounds depend on both BB and n−Bn-B. Our analysis first gives bounds in terms of BB and the total number of clients nn. The following observation sharpens the dependence on nn to one on n−Bn-B: singleton batches can be handled at constant competitive ratio, while nonsingleton batches contain at most 2(n−B)2(n-B) clients.

Observation 2.2 (Singleton–nonsingleton transfer). Suppose a batched random-order algorithm satisfies

E[ALG]≤aOPTconn+CRBR(m)OPTopen\mathbb{E}[\mathrm{ALG}] \le a\mathrm{OPT}_{\mathrm{conn}}+\mathrm{CR}_{\mathrm{BR}}(m)\mathrm{OPT}_{\mathrm{open}}

on instances with at most mm clients, where aa is a constant and CRBR\mathrm{CR}_{\mathrm{BR}} is nondecreasing. Assume the same bound holds against every fixed feasible comparison solution. If an ordinary random-order algorithm in the same opening-cost model has competitive ratio CRRO\mathrm{CR}_{\mathrm{RO}}, then the cost ALGcomb\mathrm{ALG}_{\mathrm{comb}} of the combined algorithm satisfies

E[ALGcomb]≤max⁡{a,CRRO}OPTconn+(CRRO+CRBR(2(n−B)))OPTopen.\mathbb{E}[\mathrm{ALG}_{\mathrm{comb}}] \le\max\{a,\mathrm{CR}_{\mathrm{RO}}\}\mathrm{OPT}_{\mathrm{conn}}+\left(\mathrm{CR}_{\mathrm{RO}}+\mathrm{CR}_{\mathrm{BR}}(2(n-B))\right)\mathrm{OPT}_{\mathrm{open}}.

Proof. Run the ordinary random-order algorithm on singleton batches and the batched algorithm on nonsingleton batches. Each copy uses its own facilities for its decisions; the combined algorithm opens their union and connects each client to the closest facility in that union. Both subsequences retain uniformly random relative order, and the nonsingleton copy receives at most ∑b:∣b∣≥2∣b∣≤2∑b:∣b∣≥2(∣b∣−1)=2(n−B)\sum_{b:|b|\ge2}|b| \le2\sum_{b:|b|\ge2}(|b|-1)=2(n-B) clients. We next compare both copies with the same optimum restricted to their clients. The restricted connection costs sum to OPTconn\mathrm{OPT}_{\mathrm{conn}}, and each restricted opening cost is at most OPTopen\mathrm{OPT}_{\mathrm{open}}. Let ALGsing\mathrm{ALG}_{\mathrm{sing}} and ALGnonsing\mathrm{ALG}_{\mathrm{nonsing}} be the costs paid by the two copies on the singleton and nonsingleton batches, respectively. Since the combined cost is at most the sum of the copies’ costs,

E[ALGcomb]≤E[ALGsing]+E[ALGnonsing]≤CRRO∑C,b: ∣b∣=1conn⁡(Cb)+a∑C,b: ∣b∣≥2conn⁡(Cb)+(CRRO+CRBR(2(n−B)))OPTopen≤max⁡{a,CRRO}OPTconn+(CRRO+CRBR(2(n−B)))OPTopen.\begin{aligned} \mathbb{E}[\mathrm{ALG}_{\mathrm{comb}}]\le\mathbb{E}[\mathrm{ALG}_{\mathrm{sing}}]+\mathbb{E}[\mathrm{ALG}_{\mathrm{nonsing}}] \\ &\le\mathrm{CR}_{\mathrm{RO}}\sum_{C,b:\,|b|=1}\operatorname{conn}(C_b)+a\sum_{C,b:\,|b|\ge2}\operatorname{conn}(C_b)+\left(\mathrm{CR}_{\mathrm{RO}}+\mathrm{CR}_{\mathrm{BR}}(2(n-B))\right)\mathrm{OPT}_{\mathrm{open}} \\ &\le\max\{a,\mathrm{CR}_{\mathrm{RO}}\}\mathrm{OPT}_{\mathrm{conn}}+\left(\mathrm{CR}_{\mathrm{RO}}+\mathrm{CR}_{\mathrm{BR}}(2(n-B))\right)\mathrm{OPT}_{\mathrm{open}}. \end{aligned}

The last inequality uses ∑C,b: ∣b∣=1conn⁡(Cb)+∑C,b: ∣b∣≥2conn⁡(Cb)=OPTconn\sum_{C,b:\,|b|=1}\operatorname{conn}(C_b)+\sum_{C,b:\,|b|\ge2}\operatorname{conn}(C_b)=\mathrm{OPT}_{\mathrm{conn}}: each client’s connection cost appears in exactly one of the two sums, so we take the maximum of their coefficients. □

Uniform opening costs

Let f>0f > 0 be the common opening cost. We first reduce the algorithm’s cost to certified openings, then to one charge per batch. A record argument bounds the number of these charges; a second bound combines records with decreases in the distance to an optimal center.

Theorem 3.1 (Uniform opening costs). For n≥1n \ge1 clients in 1≤B≤n1 \le B \le n batches, there exists an algorithm satisfying

E[ALG]≤O(1)OPTconn+O(min⁡{log⁡(B+1),log⁡(n−B+2)})OPTopen.\mathbb{E}[\mathrm{ALG}] \le O(1)\mathrm{OPT}_{\mathrm{conn}} + O\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right)\mathrm{OPT}_{\mathrm{open}}.

The algorithm and its certificates

Our algorithm consists of running two parallel versions of Meyerson’s algorithm, one that will give us the guarantee for singleton batches (pure random order) and one for nonsingleton ones. This allows us to use Observation 2.2. Since the algorithm is the same, just run in parallel, we describe it once next. Namely, on the arrival of vv, Meyerson’s algorithm [17] opens a facility at vv with probability

pv=min⁡{1,d(v,Fv)f},p_v=\min\left\{1,\frac{d(v,F_v)}{f}\right\},

and otherwise it connects vv to a closest open facility. The first client opens surely. We write FvF_v and Fv+F_v^{+} for the facility sets immediately before and after processing vv. Similarly, Hv\mathcal{H}_v contains the execution history up to the arrival of vv, including its identity but not its lottery outcomes, while Hv+\mathcal{H}_v^{+} also includes the lotteries and decisions made when processing vv.

We use the same random variable for Meyerson’s opening decision: that is, for every client vv, sample Uv∼Unif⁡(0,1)U_v \sim\operatorname{Unif}(0,1), independently across clients and independently of both random arrival orders. We then realize Meyerson’s decision by opening at vv exactly when fUv≤d(v,Fv)fU_v \le d(v,F_v). From here on, the main idea is to use a more restrictive event called a certified opening, which follows the balanced-opening idea of Huang and Jiang [10]. In particular, fixed a comparison cluster CC with center cc, we give each client v∈Cv \in C the key Zv=d(c,v)+fUvZ_v=d(c,v)+fU_v, and call vv certified if

Zv≤min⁡{f,d(c,Fv)}.(1)Z_v \le\min\{f,d(c,F_v)\}. \tag*{(1)}

Certification implies an opening at vv, since fUv≤d(c,Fv)−d(c,v)≤d(v,Fv)fU_v \le d(c,F_v)-d(c,v) \le d(v,F_v), and hence d(c,Fv+)≤d(c,v)<Zvd(c,F_v^{+}) \le d(c,v) < Z_v. The converse need not hold: there can be openings that are not certified. Hence, the analysis must charge the entire cost the algorithm incurs to these specific type of charges, which is exactly what we do in Lemma 3.2. In addition, the reason the certification definition in (1) has a cap at ff is because this will let us bound the number of certifications directly. To this end, we define

Yv=f1{v is certified},Wb=f1{∃v∈Cb:v is certified},WC=∑bWb.Y_v=f\mathbf{1}_{\{v\text{ is certified}\}}, \qquad W_b=f\mathbf{1}_{\{\exists v\in C_b:v\text{ is certified}\}}, \qquad W_C=\sum_b W_b.

Hence, YvY_v counts the opening cost if client vv is certified and WbW_b the opening cost if there is a client $v \in C_b that is certified. We also let KC=WC/fK_C = W_C/f be the number of batches containing a certification from CC.

Reducing cost to certified charges

Lemma 3.2. It holds that

E[ALG⁡(C)]≤4conn⁡(C)+2E[∑v∈CYv].\mathbb{E}[\operatorname{ALG}(C)] \le4\operatorname{conn}(C) + 2\mathbb{E}\left[\sum_{v\in C}Y_v\right].

Proof. The bound above follows by summing over v∈Cv \in C the inequality below and taking expectations:

E[cost⁡(v)∣Hv]≤2min⁡{f,d(v,Fv)}≤2E[Yv∣Hv]+4d(c,v).\mathbb{E}[\operatorname{cost}(v)\mid\mathcal{H}_v] \le2\min\{f,d(v,F_v)\} \le2\mathbb{E}[Y_v\mid\mathcal{H}_v] + 4d(c,v).

We start by proving the first inequality. Clearly, if Fv=∅F_v=\varnothing, the cost is ff, whereas, if Fv≠∅F_v\ne\varnothing,

E[cost⁡(v)∣Hv]=fpv+d(v,Fv)(1−pv)≤2fpv=2min⁡{f,d(v,Fv)}.\mathbb{E}[\operatorname{cost}(v)\mid\mathcal{H}_v] = fp_v + d(v,F_v)(1-p_v) \le2fp_v = 2\min\{f,d(v,F_v)\}.

Indeed, the connection term is zero if pv=1p_v=1, and is otherwise d(v,Fv)=fpvd(v,F_v)=fp_v. For the second inequality, observe that, conditional on the history Hv\mathcal{H}_v just before processing vv, we have E[Yv∣Hv]=[min⁡{f,d(c,Fv)}−d(c,v)]+\mathbb{E}[Y_v\mid\mathcal{H}_v]=[\min\{f,d(c,F_v)\}-d(c,v)]_+. Therefore, by triangle inequality,

min⁡{f,d(v,Fv)}≤min⁡{f,d(c,Fv)}+d(c,v)≤[min⁡{f,d(c,Fv)}−d(c,v)]++2d(c,v)=E[Yv∣Hv]+2d(c,v).\begin{aligned} \min\{f,d(v,F_v)\}\le\min\{f,d(c,F_v)\}+d(c,v)\le[\min\{f,d(c,F_v)\}-d(c,v)]_+ + 2d(c,v) \\ &= \mathbb{E}[Y_v\mid\mathcal{H}_v]+2d(c,v). \end{aligned}

To conclude, we note that for Fv=∅F_v=\varnothing, both capped distances are ff, so the same calculation applies. □\square

Summing charges within a batch

With a single opening price, the probability of certification decreases with the distance to cc. This lets us charge all certifications after the first directly to connection distances.

Lemma 3.3 (Total certified charge of a batch). For every batch bb,

E[∑v∈CbYv]≤E[Wb]+conn⁡(Cb).\mathbb{E}\left[\sum_{v\in C_b}Y_v\right]\le\mathbb{E}[W_b]+\operatorname{conn}(C_b).

Proof. We charge the first certification to WbW_b and show that all later certifications contribute at most conn⁡(Cb)\operatorname{conn}(C_b) in expectation. We fix a position in the shuffled batch and write vv for the client occupying it. Let H\mathcal{H} contain the execution history before exposing vv, and consider a history in which no client of CbC_b has yet been certified. We stress that H\mathcal{H} is the history before exposing the next client vv; revealing its identity gives Hv\mathcal{H}_v, while its lottery remains unexposed. We next write S⊆CbS\subseteq C_b for the unprocessed clients and t=min⁡{f,d(c,F)}t=\min\{f,d(c,F)\} for the current facility set FF. We condition further on the event E={v∈S, v is certified}\mathcal{E}=\{v\in S,\ v\text{ is certified}\}, whenever P(E∣H)>0\mathbb{P}(\mathcal{E}\mid\mathcal{H})>0. Therefore, the first certified client’s expected distance satisfies

E[d(c,v)∣H,E]=∑w∈Sd(c,w)P(v=w∣H,E)=∑w∈Sd(c,w)[t−d(c,w)]+∑w∈S[t−d(c,w)]+≤conn⁡(S)∣S∣.\mathbb{E}[d(c,v)\mid\mathcal{H},\mathcal{E}] =\sum_{w\in S}d(c,w)\mathbb{P}(v=w\mid\mathcal{H},\mathcal{E}) =\frac{\sum_{w\in S}d(c,w)[t-d(c,w)]_+}{\sum_{w\in S}[t-d(c,w)]_+} \le\frac{\operatorname{conn}(S)}{|S|}.

The second equality above follows since each remaining client is equally likely to come next, and since w∈Sw \in S is certified with probability [t−d(c,w)]+/f[t-d(c,w)]_{+}/f. Thus,

P(v=w∣H,E)=[t−d(c,w)]+∑u∈S[t−d(c,u)]+.\mathbb{P}(v=w\mid\mathcal{H},\mathcal{E})=\frac{[t-d(c,w)]_{+}}{\sum_{u\in S}[t-d(c,u)]_{+}}.

For the inequality, we use the fact that these weights decrease with distance to cc. Indeed, for every u,w∈Su,w\in S,

(d(c,u)−d(c,w))([t−d(c,u)]+−[t−d(c,w)]+)≤0,(d(c,u)-d(c,w))([t-d(c,u)]_{+}-[t-d(c,w)]_{+})\leq0,

and thus summing over u,w∈Su,w\in S and rearranging gives

∣S∣∑w∈Sd(c,w)[t−d(c,w)]+≤conn⁡(S)∑w∈S[t−d(c,w)]+.|S|\sum_{w\in S}d(c,w)[t-d(c,w)]_{+}\leq\operatorname{conn}(S)\sum_{w\in S}[t-d(c,w)]_{+}.

On event E\mathcal{E}, a facility opens at vv, and therefore every later client w∈S∖{v}w\in S\setminus\{v\} has d(c,Fw)≤d(c,v)d(c,F_w)\leq d(c,v). Its lottery is still fresh conditional on Hw\mathcal{H}_w, giving

E[Yw∣Hw]=[min⁡{f,d(c,Fw)}−d(c,w)]+≤d(c,v).\mathbb{E}[Y_w\mid\mathcal{H}_w]=[\min\{f,d(c,F_w)\}-d(c,w)]_{+}\leq d(c,v).

We sum over these later clients and take conditional expectations again to obtain

E[∑w∈S∖{v}Yw ∣ H,E]≤(∣S∣−1)E[d(c,v)∣H,E]≤∣S∣−1∣S∣conn⁡(S)≤conn⁡(Cb).\mathbb{E}\left[\left.\sum_{w\in S\setminus\{v\}}Y_w\ \right|\ \mathcal{H},\mathcal{E}\right]\leq(|S|-1)\mathbb{E}[d(c,v)\mid\mathcal{H},\mathcal{E}]\leq\frac{|S|-1}{|S|}\operatorname{conn}(S)\leq\operatorname{conn}(C_b).

This bound holds at every possible position of the first certification and for every preceding history. Averaging over these mutually exclusive possibilities, and adding the first charge WbW_b, proves the lemma. □

Summing over batches and using Lemma 3.2 immediately gives the following corollary.

Corollary 3.4. It holds that

E[ALG⁡(C)]≤6conn⁡(C)+2fE[KC].\mathbb{E}[\operatorname{ALG}(C)]\leq6\operatorname{conn}(C)+2f\mathbb{E}[K_C].

Bounding the first certifications

For each batch with Cb≠∅C_b\ne\varnothing, let Qb=min⁡v∈CbZvQ_b=\min_{v\in C_b}Z_v; batches with Cb=∅C_b=\varnothing contribute zero and can be omitted. We give two bounds on KCK_C: one in terms of the number of batches, and one in terms of the number of clients and their connection distances.

Lemma 3.5 (Record bound). For every comparison cluster CC, E[KC]≤HB\mathbb{E}[K_C]\leq H_B.

Proof. After processing any v∈Cv\in C, min⁡{f,d(c,Fv+)}<Zv\min\{f,d(c,F_v^{+})\}<Z_v. Indeed, if the threshold was already below ZvZ_v, it remains below; otherwise vv is certified and min⁡{f,d(c,Fv+)}≤d(c,v)<Zv\min\{f,d(c,F_v^{+})\}\leq d(c,v)<Z_v. Applying this to a client attaining Qb′Q_{b'} shows that the threshold remains below Qb′Q_{b'} after batch b′b'. Thus a certified client vv in a later batch bb gives

Qb≤Zv≤min⁡{f,d(c,Fv)}<Qb′.Q_b\leq Z_v\leq\min\{f,d(c,F_v)\}<Q_{b'}.

Every batch counted by KCK_C is therefore a lower record of the batch keys. Write Q1,…,QsQ_1,\ldots,Q_s for the keys of the batches meeting CC, where s≤Bs\leq B, and let π1,…,πs\pi_1,\ldots,\pi_s be their arrival order. Conditional on these keys,

which are distinct almost surely, π\pi remains a uniformly random permutation. Hence

E[KC∣Q1,…,Qs]≤∑r=1sP(Qπr=min⁡ℓ≤rQπℓ∣Q1,…,Qs)=∑r=1s1r=Hs≤HB.\mathbb{E}[K_C \mid Q_1,\ldots,Q_s] \le\sum_{r=1}^{s} \mathbb{P}\left(Q_{\pi_r}=\min_{\ell\le r}Q_{\pi_\ell}\mathrel{\Big|} Q_1,\ldots,Q_s\right)=\sum_{r=1}^{s}\frac{1}{r}=H_s\le H_B.

The equality follows because each of the first rr positions is equally likely to contain their smallest key. Taking expectations proves the lemma. □

Lemma 3.6 (Progress and records). For every ρ>1\rho>1,

E[KC]≤3+log⁡nlog⁡ρ+log⁡(1+(ρ−1)conn⁡(C)f).\mathbb{E}[K_C]\le3+\frac{\log n}{\log\rho}+\log\left(1+\frac{(\rho-1)\operatorname{conn}(C)}{f}\right).

Proof. Count the first certified client of CbC_b in each batch. Their number is exactly KCK_C. The certification threshold min⁡{f,d(c,F)}\min\{f,d(c,F)\} starts at most ff and never increases. We distinguish three cases.

(1) Multiplicative progress. If min⁡{f,d(c,Fv)}>f/n\min\{f,d(c,F_v)\}>f/n and d(c,v)≤min⁡{f,d(c,Fv)}/ρd(c,v)\le\min\{f,d(c,F_v)\}/\rho, certification gives

min⁡{f,d(c,Fv+)}≤d(c,v)≤min⁡{f,d(c,Fv)}ρ.\min\{f,d(c,F_v^+)\}\le d(c,v)\le\frac{\min\{f,d(c,F_v)\}}{\rho}.

Before the rrth such certification, f/n<min⁡{f,d(c,Fv)}≤f/ρr−1f/n<\min\{f,d(c,F_v)\}\le f/\rho^{r-1}, and thus r≤1+log⁡n/log⁡ρr\le1+\log n/\log\rho, which means that this case contributes at most 1+log⁡n/log⁡ρ1+\log n/\log\rho.

(2) Small certification threshold. If min⁡{f,d(c,Fv)}≤f/n\min\{f,d(c,F_v)\}\le f/n, then

P(v is certified∣Hv)=[min⁡{f,d(c,Fv)}−d(c,v)]+f≤1n.\mathbb{P}(v\text{ is certified}\mid H_v)=\frac{[\min\{f,d(c,F_v)\}-d(c,v)]_+}{f}\le\frac{1}{n}.

For every history, a client either fails the small-threshold condition and contributes zero to this case, or is certified with probability at most 1/n1/n. The expected count is therefore at most ∑v∈C1/n≤1\sum_{v\in C}1/n\le1.

(3) Remaining certifications. Here d(c,v)>min⁡{f,d(c,Fv)}/ρd(c,v)>\min\{f,d(c,F_v)\}/\rho, so

fUv≤min⁡{f,d(c,Fv)}−d(c,v)<(ρ−1)d(c,v).fU_v\le\min\{f,d(c,F_v)\}-d(c,v)<(\rho-1)d(c,v).

Call a batch suspect if it contains a client v∈Cbv\in C_b satisfying fUv<(ρ−1)d(c,v)fU_v<(\rho-1)d(c,v), and let NN count these batches. A union bound gives

E[N]≤∑v∈CP(fUv<(ρ−1)d(c,v))=∑v∈Cmin⁡{1,(ρ−1)d(c,v)f}≤(ρ−1)conn⁡(C)f.\mathbb{E}[N]\le\sum_{v\in C}\mathbb{P}(fU_v<(\rho-1)d(c,v))=\sum_{v\in C}\min\left\{1,\frac{(\rho-1)d(c,v)}{f}\right\}\le\frac{(\rho-1)\operatorname{conn}(C)}{f}.

Conditioning on all lottery variables fixes the suspect batches and their keys, while their relative order remains uniform. Every remaining counted batch is a lower record also among suspect batches, by the preceding lemma. Its conditional expected count is therefore at most ∑r=1N1/r=HN\sum_{r=1}^{N}1/r=H_N. Taking expectations and applying Jensen’s inequality,

E[HN]≤1+E[log⁡(1+N)]≤1+log⁡(1+E[N])≤1+log⁡(1+(ρ−1)conn⁡(C)f).\mathbb{E}[H_N] \le1 + \mathbb{E}[\log(1+N)] \le1 + \log(1+\mathbb{E}[N]) \le1 + \log\left(1+\frac{(\rho-1)\operatorname{conn}(C)}{f}\right).

Adding the three bounds proves the lemma.

We now combine all of the above to finish the proof of Theorem 3.1.

Proof of Theorem 3.1. First, let us choose ρ=exp⁡(max⁡{1,log⁡(n+1)})\rho= \exp(\max\{1,\sqrt{\log(n+1)}\}), and apply Corollary 3.4 and Lemmas 3.5 and 3.6, to obtain

E[ALG⁡(C)]≤8conn⁡(C)+12f⋅min⁡{log⁡(B),log⁡(n)}.\mathbb{E}[\operatorname{ALG}(C)] \le8\operatorname{conn}(C) + 12f\cdot\min\left\{\log(B),\sqrt{\log(n)}\right\}.

Then, summing over the optimal clusters and applying Observation 2.2 proves

E[ALG⁡combined]≤O(1)OPT⁡conn+O(min⁡{log⁡(B+1),log⁡(n−B+2)})OPT⁡open.\mathbb{E}[\operatorname{ALG}_{\mathrm{combined}}] \le O(1)\operatorname{OPT}_{\mathrm{conn}} + O\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right)\operatorname{OPT}_{\mathrm{open}}.

Nonuniform opening costs

We extend the uniform analysis using charges at powers of two: we compare clients’ total charges across levels within each batch, then use geometric charging to apply the uniform record and progress bounds.

Theorem 4.1 (Nonuniform opening costs). For n≥1n \ge1 clients in 1≤B≤n1 \le B \le n batches, there exists an algorithm satisfying

E[ALG⁡]≤O(1)OPT⁡conn+O(min⁡{log⁡(B+1),log⁡(n−B+2)})OPT⁡open.\mathbb{E}[\operatorname{ALG}] \le O(1)\operatorname{OPT}_{\mathrm{conn}} + O\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right)\operatorname{OPT}_{\mathrm{open}}.

The algorithm and its certificates

Before describing the algorithm and carrying out its analysis, we simplify our problem by rounding up opening costs up to powers of two, so f(y)≤f^(y)<2f(y)f(y) \le\hat{f}(y) < 2f(y), and letting f1<⋯<fmf_1 < \cdots< f_m be the distinct rounded costs. We also denote the set of facilities of cost at most fjf_j as Mj={y:f^(y)≤fj}M_j = \{y : \hat{f}(y) \le f_j\}, with dv(j)=d(v,Mj)d_v^{(j)} = d(v,M_j) and dv(0)=∞d_v^{(0)} = \infty. Every client location is permitted, so dv(m)=0d_v^{(m)} = 0.

We use again Meyerson’s marginal rule [17], which uses the facility set FvF_v present before processing vv. More specifically, let us write Δv(0)=d(v,Fv)\Delta_v^{(0)} = d(v,F_v) and Δv(j)=min⁡{d(v,Fv),dv(j)}\Delta_v^{(j)} = \min\{d(v,F_v),d_v^{(j)}\}, and, independently at each level jj, we let the algorithm select a closest point of Fv∪MjF_v \cup M_j with probability

pv(j)=min⁡{1,Δv(j−1)−Δv(j)fj},(2)p_v^{(j)} = \min\left\{1,\frac{\Delta_v^{(j-1)}-\Delta_v^{(j)}}{f_j}\right\}, \tag*{(2)}

opening every selected facility that is not already open, paying its original cost, and connecting vv to a closest facility in the resulting set Fv+F_v^+. All lotteries use the same pre-client set FvF_v and fixed distance tie breaking, and when Fv=∅F_v = \varnothing, the first lottery succeeds surely. We realize that the right-hand side of (2) is equal to the marginal decrease of the distance to the closest facility when the set of facilities Mj∖Mj−1M_j \setminus M_{j-1} of level jj is added to Mj−1∪FvM_{j-1} \cup F_v.

We aim to mirror the coupling used in the uniform case. To this end, using independent Uv(j)∼Unif⁡(0,1)U_v^{(j)} \sim\operatorname{Unif}(0,1) (also independent of all arrival orders), the level-jj lottery succeeds precisely when

dv(j)+fjUv(j)≤min⁡{d(v,Fv),dv(j−1)}.(3)d_v^{(j)} + f_j U_v^{(j)} \le\min\{d(v,F_v),d_v^{(j-1)}\}. \tag*{(3)}

Indeed, its probability is min⁡{1,[min⁡{d(v,Fv),dv(j−1)}−dv(j)]+/fj}=pv(j)\min\{1,[\min\{d(v,F_v),d_v^{(j-1)}\}-d_v^{(j)}]_+/f_j\}=p_v^{(j)}. Upon success, positivity of Uv(j)U_v^{(j)} implies that the selected facility belongs to MjM_j and is at distance dv(j)d_v^{(j)} from vv.

We next fix a comparison cluster CC with center cc, and write fC=fjCf_C=f_{j_C} for its rounded opening cost. Similarly to the uniform case, for v∈Cv\in C, we give each client-level pair (v,j)(v,j) the static key

Zv(j)=d(c,v)+dv(j)+fjUv(j),(4)Z_v^{(j)} = d(c,v)+d_v^{(j)}+f_jU_v^{(j)}, \tag*{(4)}

setting it to ∞\infty if dv(j)+fjUv(j)>dv(j−1)d_v^{(j)}+f_jU_v^{(j)}>d_v^{(j-1)}. We say that the client-level pair (v,j)(v,j) is certified if its key is finite and Zv(j)≤d(c,Fv)Z_v^{(j)}\le d(c,F_v). Certification implies a successful lottery, since d(v,Fv)≥d(c,Fv)−d(c,v)d(v,F_v)\ge d(c,F_v)-d(c,v), and gives

d(c,F+)≤d(c,v)+dv(j)<Zv(j).(5)d(c,F^+) \le d(c,v)+d_v^{(j)} < Z_v^{(j)}. \tag*{(5)}

We stress that being certified is a sufficient condition for opening but is not necessary. Following the above, we define

Yv=∑j≤jCfj1{(v,j) is certified}Y_v=\sum_{j\le j_C} f_j\mathbf{1}_{\{(v,j)\text{ is certified}\}}

as the total cost of certified openings induced by client vv within cost level jCj_C (the rounded opening cost of the optimal facility serving cluster CC). As we will see, we retain only up until this level because all the more expensive levels can be charged directly to the optimal connection cost. Similarly, for each batch Cb=C∩bC_b=C\cap b, let WbW_b charge fjf_j once for each level j≤jCj\le j_C with at least one certified client in CbC_b, i.e.,

Wb:=∑j≤jCfj1{∃v∈Cb:(v,j) is certified},W_b:=\sum_{j\le j_C}f_j\mathbf{1}_{\{\exists v\in C_b:(v,j)\text{ is certified}\}},

and put WC=∑bWbW_C=\sum_b W_b. Thus WbW_b pays fjf_j once if at least one client of CbC_b is certified at level jj, regardless of how many such certifications occur, while YvY_v counts all certified charges.

Reducing cost to certified charges

Lemma 4.2 (Reduction to certified charges). For every comparison cluster CC,

E[ALG⁡(C)]≤6conn⁡(C)+2E[∑v∈CYv].\mathbb{E}[\operatorname{ALG}(C)]\le6\operatorname{conn}(C)+2\mathbb{E}\left[\sum_{v\in C}Y_v\right].

Our strategy to prove the above lemma will be similar to the uniform case. We will in fact prove that

E[cost⁡(v)∣Hv]≤6d(c,v)+2E[Yv∣Hv],\mathbb{E}[\operatorname{cost}(v)\mid\mathcal{H}_v] \le6d(c,v)+2\mathbb{E}[Y_v\mid\mathcal{H}_v],

for every client. Once this is shown, the lemma simply follows by taking expectations and summing. To this end, let us first fix vv and condition on Hv\mathcal{H}_v, proving the following claim.

Claim 4.3. Fix vv and condition on Hv\mathcal{H}_v. Then, it holds that

E[cost⁡(v)∣Hv]≤∑j=1mfjpv(j)+E[d(v,Fv+)∣Hv]≤2∑j=1mfjpv(j).(6)\mathbb{E}[\operatorname{cost}(v)\mid\mathcal{H}_v]\le\sum_{j=1}^{m}f_jp_v^{(j)}+\mathbb{E}[d(v,F_v^+)\mid\mathcal{H}_v]\le2\sum_{j=1}^{m}f_jp_v^{(j)}. \tag*{(6)}

Proof. Fixed vv and conditioned on Hv\mathcal{H}_v, we know that each newly opened facility is selected by a successful lottery, and a level-jj lottery selects at most one facility, whose opening cost is at most fjf_j. Hence, for every outcome,

∑y∈Fv+∖Fvf(y)≤∑j=1mfj1{level-j lottery succeeds}.\sum_{y\in F_v^+\setminus F_v}f(y)\le\sum_{j=1}^{m}f_j\mathbf{1}_{\{\text{level-}j\text{ lottery succeeds}\}}.

Thus, taking conditional expectations gives

E[∑y∈Fv+∖Fvf(y)∣Hv]≤∑j=1mfjP(level-j lottery succeeds∣Hv)=∑j=1mfjpv(j).\mathbb{E}\left[\left.\sum_{y\in F_v^+\setminus F_v}f(y)\right|\mathcal{H}_v\right]\le\sum_{j=1}^{m}f_j\mathbb{P}(\text{level-}j\text{ lottery succeeds}\mid\mathcal{H}_v)=\sum_{j=1}^{m}f_jp_v^{(j)}.

We next show that ∑j=1mfjpv(j)\sum_{j=1}^{m}f_jp_v^{(j)} also bounds the expected connection cost. The key observation is that the final connection distance is at most the sum of the marginal gaps at failed levels. Indeed, suppose first that Fv≠∅F_v\ne\varnothing and at least one lottery succeeds, and let kk be the largest successful level. Its selected facility is within distance Δv(k)\Delta_v^{(k)} of vv, and every level above kk fails. Since Δv(m)=0\Delta_v^{(m)}=0, we obtain

d(v,Fv+)≤Δv(k)=∑j>k(Δv(j−1)−Δv(j))≤∑j=1m(Δv(j−1)−Δv(j))1{level-j lottery fails}.d(v,F_v^+)\le\Delta_v^{(k)}=\sum_{j>k}\left(\Delta_v^{(j-1)}-\Delta_v^{(j)}\right)\le\sum_{j=1}^{m}\left(\Delta_v^{(j-1)}-\Delta_v^{(j)}\right)\mathbf{1}_{\{\text{level-}j\text{ lottery fails}\}}.

where the last inequality adds the nonnegative gaps of any failed levels below kk. If every lottery fails, the last sum telescopes to Δv(0)=d(v,Fv)\Delta_v^{(0)}=d(v,F_v), so the same bound holds. Taking conditional expectations, when Fv≠∅F_v\ne\varnothing we obtain

E[d(v,Fv+)∣Hv]≤∑j=1m(Δv(j−1)−Δv(j))(1−pv(j))≤∑j=1mfjpv(j).\mathbb{E}[d(v,F_v^+)\mid\mathcal{H}_v]\le\sum_{j=1}^{m}\left(\Delta_v^{(j-1)}-\Delta_v^{(j)}\right)(1-p_v^{(j)})\le\sum_{j=1}^{m}f_jp_v^{(j)}.

The last inequality holds term by term: if pv(j)=1p_v^{(j)}=1, the contribution is zero, and otherwise, Δv(j−1)−Δv(j)=fjpv(j)\Delta_v^{(j-1)}-\Delta_v^{(j)}=f_jp_v^{(j)} and 1−pv(j)≤11-p_v^{(j)}\le1. If Fv=∅F_v=\varnothing, the first lottery succeeds surely, so the same telescoping argument and expectation bound apply with both sums starting at j=2j=2, where all gaps are finite. Adding the nonnegative term f1pv(1)f_1p_v^{(1)} to the final bound gives the same conclusion. Combining this connection-cost bound with the opening-cost bound proved above yields, in all cases,

E[cost⁡(v)∣Hv]≤∑j=1mfjpv(j)+E[d(v,Fv+)∣Hv]≤2∑j=1mfjpv(j).\mathbb{E}[\operatorname{cost}(v)\mid\mathcal{H}_v]\le\sum_{j=1}^{m}f_jp_v^{(j)}+\mathbb{E}[d(v,F_v^+)\mid\mathcal{H}_v]\le2\sum_{j=1}^{m}f_jp_v^{(j)}.

It remains to compare the lottery charges to the expected certified cost YvY_v, as we do next.

Claim 4.4. Fix vv and condition on Hv\mathcal{H}_v. Then, it holds that

∑j=1mfjpv(j)≤E[Yv∣Hv]+3d(c,v).\sum_{j=1}^{m}f_jp_v^{(j)}\le\mathbb{E}[Y_v\mid\mathcal{H}_v]+3d(c,v).

Proof. We will show that replacing lottery charges by certified charges at all levels loses at most 2d(c,v)2d(c,v) in expectation. Removing the levels above jCj_C then loses at most another d(c,v)d(c,v), giving the desired bound.

Condition on Hv\mathcal{H}_v and suppose first that Fv≠∅F_v\ne\varnothing. The triangle inequality gives

[d(c,Fv)−d(c,v)]+≤d(v,Fv)≤[d(c,Fv)−d(c,v)]++2d(c,v).[d(c,F_v)-d(c,v)]_+\le d(v,F_v)\le[d(c,F_v)-d(c,v)]_++2d(c,v).

At level jj, the expected lottery charge is min⁡{fj,Δv(j−1)−Δv(j)}\min\{f_j,\Delta_v^{(j-1)}-\Delta_v^{(j)}\}, whereas the expected certified charge is

fjP((v,j) is certified∣Hv)=min⁡{fj,min⁡{[d(c,Fv)−d(c,v)]+,dv(j−1)}−min⁡{[d(c,Fv)−d(c,v)]+,dv(j)}}.f_j\mathbb{P}((v,j)\text{ is certified}\mid\mathcal{H}_v) =\min\left\{f_j,\min\{[d(c,F_v)-d(c,v)]_+,d_v^{(j-1)}\}-\min\{[d(c,F_v)-d(c,v)]_+,d_v^{(j)}\}\right\}.

The marginal length in the second expression is no larger than Δv(j−1)−Δv(j)\Delta_v^{(j-1)}-\Delta_v^{(j)}, since its cutoff is no larger than d(v,Fv)d(v,F_v). Using min⁡{fj,x}−min⁡{fj,y}≤x−y\min\{f_j,x\}-\min\{f_j,y\}\le x-y for x≥y≥0x\ge y\ge0, we obtain

∑j=1mfjpv(j)−E[∑j=1mfj1{(v,j) is certified}∣Hv]≤∑j=1m(Δv(j−1)−Δv(j)−min⁡{[d(c,Fv)−d(c,v)]+,dv(j−1)}+min⁡{[d(c,Fv)−d(c,v)]+,dv(j)})=d(v,Fv)−[d(c,Fv)−d(c,v)]+≤2d(c,v).\begin{aligned} \sum_{j=1}^{m}f_jp_v^{(j)}-\mathbb{E}\left[\left.\sum_{j=1}^{m}f_j\mathbf{1}_{\{(v,j)\text{ is certified}\}}\right|\mathcal{H}_v\right] \le\sum_{j=1}^{m}\left(\Delta_v^{(j-1)}-\Delta_v^{(j)}-\min\{[d(c,F_v)-d(c,v)]_+,d_v^{(j-1)}\}+\min\{[d(c,F_v)-d(c,v)]_+,d_v^{(j)}\}\right) \\ &=d(v,F_v)-[d(c,F_v)-d(c,v)]_+\le2d(c,v). \end{aligned}

The equality follows by telescoping, using Δv(0)=d(v,Fv)\Delta_v^{(0)}=d(v,F_v), dv(0)=∞d_v^{(0)}=\infty, and Δv(m)=dv(m)=0\Delta_v^{(m)}=d_v^{(m)}=0. If Fv=∅F_v=\varnothing, success and certification both reduce to dv(j)+fjUv≤dv(j−1)d_v^{(j)}+f_jU_v\le d_v^{(j-1)}. their expected charges are therefore equal, so the bound also holds.

It remains to account for the certified charges above level jCj_C, which are not included in YvY_v: each is bounded in expectation by the length of its marginal interval, so

E[∑j>jCfj1{(v,j) is certified}∣Hv]≤∑j>jC(dv(j−1)−dv(j))=dv(jC)≤d(c,v).\mathbb{E}\left[\left.\sum_{j>j_C}f_j\mathbf{1}_{\{(v,j)\text{ is certified}\}}\right|\mathcal{H}_v\right]\le\sum_{j>j_C}(d_v^{(j-1)}-d_v^{(j)})=d_v^{(j_C)}\le d(c,v).

The equality uses dv(m)=0d_v^{(m)}=0, and the last inequality follows from c∈MjCc\in M_{j_C}. Substituting this bound above and using the definition of YvY_v gives

∑j=1mfjpv(j)≤E[Yv∣Hv]+3d(c,v).\sum_{j=1}^{m} f_j p_v^{(j)} \le\mathbb{E}[Y_v \mid\mathcal{H}_v] + 3d(c,v).

We can now finish the proof of Lemma 4.2.

Proof. Combining the bound in Claim 4.3 with the one in Claim 4.4 reaches the desired final bound:

E[cost⁡(v)∣Hv]≤2∑j=1mfjpv(j)≤4d(c,v)+2E[∑j=1mfj1{(v,j) is certified}∣Hv]≤6d(c,v)+2E[Yv∣Hv].\begin{aligned} \mathbb{E}[\operatorname{cost}(v) \mid\mathcal{H}_v] &\le2\sum_{j=1}^{m} f_jp_v^{(j)} \le4d(c,v)+2\mathbb{E}\left[\left.\sum_{j=1}^{m}f_j\mathbf{1}\{(v,j)\text{ is certified}\}\right|\mathcal{H}_v\right] \\ &\le6d(c,v)+2\mathbb{E}[Y_v\mid\mathcal{H}_v]. \end{aligned}

Taking expectations and summing over v∈Cv \in C proves the lemma.

Summing charges within a batch

As we saw in the earlier section, Lemma 4.2 bounds each client’s cost in terms of its certified charge and its distance to cc. We next bound, as in Lemma 3.3 for the uniform opening cost case, the total certified charge of a batch by its connection cost and the charges for first certifications. Here, WbW_b charges fjf_j once for each level j≤jCj \le j_C at which some client in CbC_b is certified.

We first bound the charges of the half of the clients closest to cc, then pair each remaining client with a distinct client in this nearer half and compare their total certified charges. Unlike in the uniform case, being closer to cc need not give a higher certification probability at a particular level: a nearer client may have zero marginal gap at that level, even when a farther client’s gap is positive.

Lemma 4.5 (Total certified charge of a batch). For every batch bb,

E[∑v∈CbYv]≤6E[Wb]+14conn⁡(Cb).\mathbb{E}\left[\sum_{v\in C_b}Y_v\right]\le6\mathbb{E}[W_b]+14\operatorname{conn}(C_b).

To prove the above lemma, we may assume that Cb≠∅C_b \ne\varnothing, since the claim is trivial when Cb=∅C_b = \varnothing. Let us call the ⌈∣Cb∣/2⌉\lceil|C_b|/2\rceil clients closest to cc near, breaking ties in a fixed way, and the others far. We first prove the following claim about near clients, and then include far ones.

Claim 4.6 (Near clients). It holds that

E[∑v nearYv]≤E[Wb]+2conn⁡(Cb).\mathbb{E}\left[\sum_{v\ \mathrm{near}}Y_v\right]\le\mathbb{E}[W_b]+2\operatorname{conn}(C_b).

Proof. We first observe that the farthest near client and all far clients give ⌊∣Cb∣/2⌋+1≥⌈∣Cb∣/2⌉\lfloor|C_b|/2\rfloor+1\ge\lceil|C_b|/2\rceil clients

at least as far from cc as every near client vv, and therefore,

conn⁡(Cb)≥(⌈∣Cb∣2⌉+1)d(c,v)≥⌈∣Cb∣2⌉d(c,v).\operatorname{conn}(C_b) \ge\left(\left\lceil\frac{|C_b|}{2}\right\rceil+1\right)d(c,v) \ge\left\lceil\frac{|C_b|}{2}\right\rceil d(c,v).

In particular, d(c,v)≤conn⁡(Cb)/⌈∣Cb∣/2⌉d(c,v) \le\operatorname{conn}(C_b)/\lceil|C_b|/2\rceil. We will charge at most WbW_b for one certification per level, and bound the remaining expected charge by 2conn⁡(Cb)/⌈∣Cb∣/2⌉2\operatorname{conn}(C_b)/\lceil|C_b|/2\rceil per near client. For each level j≤jCj \le j_C, consider the condition

d(c,F)≤d(c,Mj)+2conn⁡(Cb)⌈∣Cb∣/2⌉,(7)d(c,F) \le d(c,M_j) + \frac{2\operatorname{conn}(C_b)}{\lceil|C_b|/2\rceil}, \tag*{(7)}

tested before the current client’s lotteries. A certification of a near client vv makes this condition true, because

d(c,Fv+)≤d(c,v)+dv(j)≤2d(c,v)+d(c,Mj)≤2conn⁡(Cb)⌈∣Cb∣/2⌉+d(c,Mj).d(c,F_v^+) \le d(c,v)+d_v^{(j)} \le2d(c,v)+d(c,M_j) \le\frac{2\operatorname{conn}(C_b)}{\lceil|C_b|/2\rceil}+d(c,M_j).

Once true, it remains true, since facilities are only added. Thus, at each level, at most one near client can be certified while the condition is false. Such a certification costs fjf_j, which is included in WbW_b, and their total charge is therefore at most WbW_b for every execution.

We next bound the charges incurred when the condition is already true. Before a near client vv is processed, let k=k(v)≤jCk=k(v)\le j_C be the highest level satisfying (7), or k=0k=0 if there is none. Note that this index is determined by Hv\mathcal{H}_v. The levels satisfying the condition form a prefix 1,…,k1,\ldots,k, since d(c,Mj)≥d(c,Mk)d(c,M_j)\ge d(c,M_k) for j≤kj\le k, and so, for a nonempty prefix, the conditional expected charge satisfies

E[∑j≤kfj1{(v,j) is certified}∣Hv]=∑j≤kmin⁡{fj,[min⁡{d(c,Fv)−d(c,v),dv(j−1)}−dv(j)]+}≤[d(c,Fv)−d(c,v)−dv(k)]+≤[d(c,Fv)−d(c,Mk)]+≤2conn⁡(Cb)⌈∣Cb∣/2⌉.\begin{aligned} \mathbb{E}\left[\left.\sum_{j\le k} f_j\mathbf{1}_{\{(v,j)\text{ is certified}\}}\right|\mathcal{H}_v\right] = \sum_{j\le k}\min\left\{f_j,\left[\min\left\{d(c,F_v)-d(c,v),d_v^{(j-1)}\right\}-d_v^{(j)}\right]_+\right\} \\ &\le\left[d(c,F_v)-d(c,v)-d_v^{(k)}\right]_+ \\ &\le\left[d(c,F_v)-d(c,M_k)\right]_+ \le\frac{2\operatorname{conn}(C_b)}{\lceil|C_b|/2\rceil}. \end{aligned}

For the first inequality, the summands are lengths of disjoint portions of the intervals (dv(j),min⁡{dv(j)+fj,dv(j−1)}]\left(d_v^{(j)},\min\{d_v^{(j)}+f_j,d_v^{(j-1)}\}\right]. For j≤kj\le k, these portions all lie above dv(k)d_v^{(k)} and below [d(c,Fv)−d(c,v)]+\left[d(c,F_v)-d(c,v)\right]_+, so their total length is at most [d(c,Fv)−d(c,v)−dv(k)]+\left[d(c,F_v)-d(c,v)-d_v^{(k)}\right]_+. The second inequality uses d(c,Mk)≤d(c,v)+dv(k)d(c,M_k)\le d(c,v)+d_v^{(k)}, and the last uses (7). An empty prefix contributes zero, including when Fv=∅F_v=\varnothing. Taking expectations and summing over the near clients now gives

E[∑v nearYv]≤E[Wb]+⌈∣Cb∣2⌉2conn⁡(Cb)⌈∣Cb∣/2⌉=E[Wb]+2conn⁡(Cb).\mathbb{E}\left[\sum_{v\ \mathrm{near}}Y_v\right] \le\mathbb{E}[W_b]+\left\lceil\frac{|C_b|}{2}\right\rceil\frac{2\operatorname{conn}(C_b)}{\lceil|C_b|/2\rceil} = \mathbb{E}[W_b]+2\operatorname{conn}(C_b).

We now turn to the far clients, by proving an inequality that allows us to pair them with a near client at a small cost.

Claim 4.7 (Far clients). For distinct u,v∈Cbu,v\in C_b,

E[Yu+Yv]≤6E[Yu]+2d(u,v).\mathbb{E}[Y_u+Y_v]\le6\mathbb{E}[Y_u]+2d(u,v).

Proof. Let us condition on the history H\mathcal{H} immediately before either client arrives, and let FF be the current facility set. Write u≺vu \prec v if uu arrives first. Swapping their positions preserves H\mathcal{H}, so each order has conditional probability 1/21/2, and both clients’ lotteries remain fresh. We first prove

E[Yv∣H,v≺u]≤2E[Yu∣H,u≺v]+2d(u,v).(8)\mathbb{E}[Y_v \mid\mathcal{H}, v \prec u] \le2\mathbb{E}[Y_u \mid\mathcal{H}, u \prec v] + 2d(u,v). \tag*{(8)}

Let ℓ≤jC\ell\le j_C be the largest level contributing its full expected charge fℓf_\ell when uu arrives first; equivalently, P((u,ℓ) is certified∣H,u≺v)=1\mathbb{P}((u,\ell)\text{ is certified} \mid\mathcal{H}, u \prec v)=1. Set ℓ=0\ell=0 and f0=0f_0=0 if there is no such level. For w∈{u,v}w \in\{u,v\} arriving first, the expected charge above ℓ\ell satisfies

∑j=ℓ+1jCmin⁡{fj,[min⁡{[d(c,F)−d(c,w)]+,dw(j−1)}−dw(j)]+}≤min⁡{[d(c,F)−d(c,w)]+,dw(ℓ)}−min⁡{[d(c,F)−d(c,w)]+,dw(jC)},\sum_{j=\ell+1}^{j_C}\min\left\{f_j,\left[\min\left\{[d(c,F)-d(c,w)]_+,d_w^{(j-1)}\right\}-d_w^{(j)}\right]_+\right\} \le\min\left\{[d(c,F)-d(c,w)]_+,d_w^{(\ell)}\right\}-\min\left\{[d(c,F)-d(c,w)]_+,d_w^{(j_C)}\right\},

where the inequality uses min⁡{fj,x}≤x\min\{f_j,x\}\le x and telescoping. Note that it is an equality for uu, since no summand above ℓ\ell reaches its cap. For F≠∅F\ne\varnothing, the triangle inequality gives ∣d(c,u)−d(c,v)∣≤d(u,v)|d(c,u)-d(c,v)|\le d(u,v) and ∣du(j)−dv(j)∣≤d(u,v)|d_u^{(j)}-d_v^{(j)}|\le d(u,v) for j≥1j\ge1. Positive parts preserve this bound, and ∣min⁡{a,b}−min⁡{a′,b′}∣≤max⁡{∣a−a′∣,∣b−b′∣}|\min\{a,b\}-\min\{a',b'\}|\le\max\{|a-a'|,|b-b'|\}. Thus each endpoint changes by at most d(u,v)d(u,v). The levels through ℓ\ell cost vv at most ∑j≤ℓfj≤2fℓ\sum_{j\le\ell}f_j\le2f_\ell, since the prices are distinct powers of two, whereas uu already pays fℓf_\ell at level ℓ\ell. Consequently,

E[Yv∣H,v≺u]≤2fℓ+(E[Yu∣H,u≺v]−fℓ)+2d(u,v)\mathbb{E}[Y_v \mid\mathcal{H},v \prec u]\le2f_\ell+\left(\mathbb{E}[Y_u \mid\mathcal{H},u \prec v]-f_\ell\right)+2d(u,v)
≤2E[Yu∣H,u≺v]+2d(u,v),\le2\mathbb{E}[Y_u \mid\mathcal{H},u \prec v]+2d(u,v),

as claimed, since fℓ≤E[Yu∣H,u≺v]f_\ell\le\mathbb{E}[Y_u \mid\mathcal{H},u \prec v]. For ℓ=0\ell=0, the prefix is empty and the first endpoint is [d(c,F)−d(c,w)]+[d(c,F)-d(c,w)]_+, which also changes by at most d(u,v)d(u,v). If F=∅F=\varnothing, level 1 contributes f1f_1, so ℓ≥1\ell\ge1. The endpoints are then dw(ℓ)d_w^{(\ell)} and dw(jC)d_w^{(j_C)}, and the same triangle-inequality bound applies.

Finally, arriving later can only decrease a client’s expected charge: facilities are only added and its lotteries remain fresh. Averaging over the two equally likely orders therefore gives

E[Yu+Yv∣H]≤E[Yu∣H,u≺v]+E[Yv∣H,v≺u]≤3E[Yu∣H,u≺v]+2d(u,v)\mathbb{E}[Y_u+Y_v\mid\mathcal{H}]\le\mathbb{E}[Y_u\mid\mathcal{H},u\prec v]+\mathbb{E}[Y_v\mid\mathcal{H},v\prec u]\le3\mathbb{E}[Y_u\mid\mathcal{H},u\prec v]+2d(u,v)
≤6E[Yu∣H]+2d(u,v).\le6\mathbb{E}[Y_u\mid\mathcal{H}]+2d(u,v).

For the first inequality, in each order the later client’s expected charge is at most its first-arrival expectation. The last inequality uses E[Yu∣H]≥1/2⋅E[Yu∣H,u≺v]\mathbb{E}[Y_u\mid\mathcal{H}]\ge1/2\cdot\mathbb{E}[Y_u\mid\mathcal{H},u\prec v]. Taking expectations proves the claim. □

Finally, we can conclude the proof of Lemma 4.5.

Proof of Lemma 4.5. We pair each far client vv with a distinct near client uu, fixing the pairing independently of the arrival order and lotteries. By Claim 4.7, we have that E[Yu+Yv]≤6E[Yu]+2d(u,v)\mathbb{E}[Y_u+Y_v]\le6\mathbb{E}[Y_u]+2d(u,v) for every pair. Hence

E[∑v∈CbYv]≤6E[∑u nearYu]+2∑(u,v) pairedd(u,v)≤6E[Wb]+14conn⁡(Cb).\mathbb{E}\left[\sum_{v\in C_b}Y_v\right]\le6\mathbb{E}\left[\sum_{u\ \mathrm{near}}Y_u\right]+2\sum_{(u,v)\ \mathrm{paired}}d(u,v)\le6\mathbb{E}[W_b]+14\operatorname{conn}(C_b).

The first inequality also covers the possible unpaired near client, since its charge is nonnegative. The second uses Claim 4.6 and the triangle inequality: ∑(u,v) pairedd(u,v)≤∑(u,v) paired(d(c,u)+d(c,v))≤conn⁡(Cb)\sum_{(u,v)\ \mathrm{paired}}d(u,v)\le\sum_{(u,v)\ \mathrm{paired}}(d(c,u)+d(c,v))\le\operatorname{conn}(C_b), because the pairs are disjoint.

Summing Lemma 4.5 over the batches and applying Lemma 4.2 gives the following proposition.

Proposition 4.8 (Reduction to first certificates). For every cluster CC,

E[ALG⁡(C)]≤34conn⁡(C)+12E[WC].\mathbb{E}[\operatorname{ALG}(C)]\le34\operatorname{conn}(C)+12\mathbb{E}[W_C].

Bounds at each opening-cost level

We now use a similar analysis of first certifications cost as the uniform case, proceeding level by level. Indeed, let KC(j)K_C^{(j)} count batches containing a level-jj certification from CC, and let LC(j)L_C^{(j)} count those containing a regular level-jj certification, which is called such if Zv(j)≤d(c,Mj)+fjZ_v^{(j)}\le d(c,M_j)+f_j.

Proposition 4.9 (Bounds at each level). For every j≤jCj\le j_C and ρ>1\rho>1,

E[KC(j)]≤HB,(9)\mathbb{E}[K_C^{(j)}]\le H_B, \tag*{(9)}
E[LC(j)]≤3+log⁡nlog⁡ρ+log⁡(1+2(ρ−1)conn⁡(C)fj).(10)\mathbb{E}[L_C^{(j)}]\le3+\frac{\log n}{\log\rho}+\log\left(1+\frac{2(\rho-1)\operatorname{conn}(C)}{f_j}\right). \tag*{(10)}

In the remainder of the argument, let us recall that j≤jCj\le j_C and let us fix the following notation. Namely, subtract the baseline d(c,Mj)d(c,M_j) from the current distance and the finite client keys, defining

qj(F)=[d(c,F)−d(c,Mj)]+,ξv(j)=d(c,v)+dv(j)−d(c,Mj),Qb(j)=min⁡v∈Cb{Zv(j)−d(c,Mj)}.q_j(F)=[d(c,F)-d(c,M_j)]_+,\qquad\xi_v^{(j)}=d(c,v)+d_v^{(j)}-d(c,M_j),\qquad Q_b^{(j)}=\min_{v\in C_b}\{Z_v^{(j)}-d(c,M_j)\}.

Thus qj(F)q_j(F) measures the excess distance to cc, which a certification reduces to at most ξv(j)\xi_v^{(j)} as we will show. Similarly, Qb(j)Q_b^{(j)} is the minimum shifted key in batch bb. It is understood that qj(∅)=∞q_j(\varnothing)=\infty and that discarded keys remain infinite.

Claim 4.10 (Certification and progress). For every v∈Cv\in C, 0≤ξv(j)≤2d(c,v)0\le\xi_v^{(j)}\le2d(c,v). Moreover, almost surely,

(v,j) is certified⟺Zv(j)<∞ and ξv(j)+fjUv(j)≤qj(Fv),(11)(v,j)\text{ is certified}\Longleftrightarrow Z_v^{(j)}<\infty\ \text{and}\ \xi_v^{(j)}+f_jU_v^{(j)}\le q_j(F_v), \tag*{(11)}
qj(Fv+)≤ξv(j)whenever (v,j) is certified.(12)q_j(F_v^+)\le\xi_v^{(j)}\qquad\text{whenever }(v,j)\text{ is certified}. \tag*{(12)}

For regular certification, replace qj(Fv)q_j(F_v) in (11) by min⁡{fj,qj(Fv)}\min\{f_j,q_j(F_v)\}.

Proof. The triangle inequality gives d(c,Mj)−d(c,v)≤dv(j)≤d(c,Mj)+d(c,v)d(c,M_j)-d(c,v) \le d_v^{(j)} \le d(c,M_j)+d(c,v). Adding d(c,v)−d(c,Mj)d(c,v)-d(c,M_j) proves 0≤ξv(j)≤2d(c,v)0 \le\xi_v^{(j)} \le2d(c,v). For a finite key,

Zv(j)−d(c,Mj)=ξv(j)+fjUv(j)>0Z_v^{(j)}-d(c,M_j)=\xi_v^{(j)}+f_jU_v^{(j)}>0

almost surely.

Subtracting the baseline from the certification test Zv(j)≤d(c,Fv)Z_v^{(j)} \le d(c,F_v) therefore gives (4.10); the positive part does not change this comparison with a positive key. Regularity additionally requires this shifted key to be at most fjf_j, giving the capped rule. Finally, a certification ensures an open facility within dv(j)d_v^{(j)} of vv, so

qj(Fv+)≤[d(c,v)+dv(j)−d(c,Mj)]+=[ξv(j)]+=ξv(j).q_j(F_v^+) \le[d(c,v)+d_v^{(j)}-d(c,M_j)]_+=[\xi_v^{(j)}]_+=\xi_v^{(j)}.

Claim 4.11 (Record bound). One has E[KC(j)]≤HB\mathbb{E}[K_C^{(j)}] \le H_B.

Proof. The claim follows by a simple record argument: we show that, for a fixed level jj, a batch key is smaller than the key of every earlier batch.

First, consider a client vv whose level-jj key is finite. We show that, after processing vv, the excess distance qj(Fv+)q_j(F_v^+) is smaller than its shifted key ξv(j)+fjUv(j)\xi_v^{(j)}+f_jU_v^{(j)}. If qj(Fv)q_j(F_v) was already smaller than this key, opening facilities can only decrease it, so qj(Fv+)≤qj(Fv)<ξv(j)+fjUv(j)q_j(F_v^+) \le q_j(F_v)<\xi_v^{(j)}+f_jU_v^{(j)}. Otherwise, the certification rule certifies (v,j)(v,j), and the resulting opening gives qj(Fv+)≤ξv(j)<ξv(j)+fjUv(j)q_j(F_v^+) \le\xi_v^{(j)} < \xi_v^{(j)}+f_jU_v^{(j)} by Claim 4.10.

Now consider a batch b′b' with Qb′(j)<∞Q_{b'}^{(j)}<\infty, and apply this observation to a client attaining its minimum shifted key Qb′(j)Q_{b'}^{(j)}. After that client is processed, qj(F)q_j(F) is strictly below Qb′(j)Q_{b'}^{(j)} and remains so, since facilities are only added. Thus, if a later batch bb contains a certified client vv, then

Qb(j)≤ξv(j)+fjUv(j)≤qj(Fv)<Qb′(j).Q_b^{(j)} \le\xi_v^{(j)}+f_jU_v^{(j)} \le q_j(F_v)<Q_{b'}^{(j)}.

The first inequality uses the definition of the batch minimum, the second uses certification, and the last follows from the preceding observation. Hence a batch containing a certification has a smaller key than every earlier batch.

Every batch counted by KC(j)K_C^{(j)} is therefore a lower record of the batch keys. Write Q1(j),…,Qs(j)Q_1^{(j)},\ldots,Q_s^{(j)} for the finite batch keys, indexed independently of their arrival order, where s≤Bs\le B, and let π1,…,πs\pi_1,\ldots,\pi_s be their arrival order. Conditional on ss and these keys, which are distinct almost surely, π\pi remains a uniformly random permutation. Hence

E[KC(j)∣Q1(j),…,Qs(j)]≤∑r=1sP(Qπr(j)=min⁡ℓ≤rQπℓ(j)∣Q1(j),…,Qs(j))=∑r=1s1r=Hs≤HB.\mathbb{E}[K_C^{(j)}\mid Q_1^{(j)},\ldots,Q_s^{(j)}] \le\sum_{r=1}^{s}\mathbb{P}\left(Q_{\pi_r}^{(j)}=\min_{\ell\le r}Q_{\pi_\ell}^{(j)}\mid Q_1^{(j)},\ldots,Q_s^{(j)}\right) =\sum_{r=1}^{s}\frac{1}{r}=H_s\le H_B.

Taking expectations gives E[KC(j)]≤HB\mathbb{E}[K_C^{(j)}]\le H_B.

Claim 4.12 (Bound for regular certifications). For every ρ>1\rho>1,

E[LC(j)]≤3+log⁡nlog⁡ρ+log⁡(1+(ρ−1)∑v∈Cξv(j)fj).\mathbb{E}[L_C^{(j)}]\le3+\frac{\log n}{\log\rho}+\log\left(1+\frac{(\rho-1)\sum_{v\in C}\xi_v^{(j)}}{f_j}\right).

Proof. We need to bound the expected number of batches containing a regular level-jj certification from CC. In each such batch, we count only the first one, so that the number counted is exactly LC(j)L_C^{(j)}. We also recall that a regular certification requires ξv(j)+fjUv(j)≤min⁡{fj,qj(Fv)}\xi_v^{(j)}+f_jU_v^{(j)}\le\min\{f_j,q_j(F_v)\}, and this certification threshold is at most fjf_j and never increases, since facilities are only added.

We divide the counted certifications into three cases as in the uniform case.

(1) Multiplicative progress. Suppose that, immediately before a counted certification, min⁡{fj,qj(Fv)}>fj/n\min\{f_j,q_j(F_v)\}>f_j/n and ξv(j)≤min⁡{fj,qj(Fv)}/ρ\xi_v^{(j)}\le\min\{f_j,q_j(F_v)\}/\rho. The certification then decreases the threshold by a factor of at least ρ\rho, because

min⁡{fj,qj(Fv+)}≤ξv(j)≤min⁡{fj,qj(Fv)}ρ.\min\{f_j,q_j(F_v^+)\}\le\xi_v^{(j)}\le\frac{\min\{f_j,q_j(F_v)\}}{\rho}.

Since the threshold starts at most fjf_j and never increases, before the rrth certification of this kind we have

fjn<min⁡{fj,qj(Fv)}≤fjρr−1⟹r<1+log⁡nlog⁡ρ.\frac{f_j}{n}<\min\{f_j,q_j(F_v)\}\le\frac{f_j}{\rho^{r-1}} \quad\Longrightarrow\quad r<1+\frac{\log n}{\log\rho}.

Thus at most 1+log⁡n/log⁡ρ1+\log n/\log\rho counted certifications belong to this case.

(2) Small certification threshold. Suppose instead that min⁡{fj,qj(Fv)}≤fj/n\min\{f_j,q_j(F_v)\}\le f_j/n. Conditional on Hv\mathcal{H}_v, the threshold is fixed and Uv(j)U_v^{(j)} is still uniform. Therefore,

P((v,j) is regularly certified∣Hv)≤[min⁡{fj,qj(Fv)}−ξv(j)]+fj≤1n.\mathbb{P}\bigl((v,j)\text{ is regularly certified}\mid\mathcal{H}_v\bigr) \le\frac{\left[\min\{f_j,q_j(F_v)\}-\xi_v^{(j)}\right]_+}{f_j} \le\frac{1}{n}.

The first inequality above follows because regular certification requires fjUv(j)≤min⁡{fj,qj(Fv)}−ξv(j)f_jU_v^{(j)}\le\min\{f_j,q_j(F_v)\}-\xi_v^{(j)} and because Uv(j)U_v^{(j)} is uniform. Moreover, certification also requires Zv(j)<∞Z_v^{(j)}<\infty, so its probability can only be smaller. For the second inequality, this follows from ξv(j)≥0\xi_v^{(j)}\ge0 and min⁡{fj,qj(Fv)}≤fj/n\min\{f_j,q_j(F_v)\}\le f_j/n. Thus each client contributes at most 1/n1/n in expectation to this case, and so summing over all clients of CC, even those whose certifications are not first in their batch, bounds the expected count by ∑v∈C1/n=∣C∣/n≤1\sum_{v\in C}1/n=|C|/n\le1.

(3) Remaining certifications. For every remaining counted certification, ξv(j)>min⁡{fj,qj(Fv)}/ρ\xi_v^{(j)}>\min\{f_j,q_j(F_v)\}/\rho, and hence

fjUv(j)≤min⁡{fj,qj(Fv)}−ξv(j)<(ρ−1)ξv(j).f_jU_v^{(j)}\le\min\{f_j,q_j(F_v)\}-\xi_v^{(j)}<(\rho-1)\xi_v^{(j)}.

We notice that every remaining counted certification belongs to a suspect batch, i.e., a batch containing v∈Cbv\in C_b with Zv(j)<∞Z_v^{(j)}<\infty and fjUv(j)<(ρ−1)ξv(j)f_jU_v^{(j)}<(\rho-1)\xi_v^{(j)}. We let NN count these batches, so that via union bound

E[N]≤∑v∈CP(fjUv(j)<(ρ−1)ξv(j))=∑v∈Cmin⁡{1,(ρ−1)ξv(j)fj}≤(ρ−1)∑v∈Cξv(j)fj.\mathbb{E}[N]\le\sum_{v\in C}\mathbb{P}\left(f_jU_v^{(j)}<(\rho-1)\xi_v^{(j)}\right) =\sum_{v\in C}\min\left\{1,\frac{(\rho-1)\xi_v^{(j)}}{f_j}\right\} \le\frac{(\rho-1)\sum_{v\in C}\xi_v^{(j)}}{f_j}.

Now, let us write Q1(j),…,QN(j)Q_1^{(j)},\ldots,Q_N^{(j)} for the keys of the suspect batches, and let π1,…,πN\pi_1,\ldots,\pi_N be their arrival order. Conditional on NN and these keys, which are distinct almost surely, π\pi remains a uniformly random permutation. By Claim 4.11, every batch counted in this case is a lower record among the suspect batches, and hence

E[number counted in this case∣Q1(j),…,QN(j)]≤∑r=1NP(Qr(j)=min⁡ℓ≤rQℓ(j)∣Q1(j),…,QN(j))=∑r=1N1r=HN.\mathbb{E}\left[\text{number counted in this case}\mid Q_1^{(j)},\ldots,Q_N^{(j)}\right]\le\sum_{r=1}^{N}\mathbb{P}\left(Q_r^{(j)}=\min_{\ell\le r}Q_\ell^{(j)}\mid Q_1^{(j)},\ldots,Q_N^{(j)}\right) =\sum_{r=1}^{N}\frac{1}{r}=H_N.

Therefore, taking expectations and applying Jensen’s inequality yields

E[number counted in this case]≤E[HN]≤1+log⁡(1+E[N])≤1+log⁡(1+(ρ−1)∑v∈Cξv(j)fj).\mathbb{E}[\text{number counted in this case}]\le\mathbb{E}[H_N]\le1+\log(1+\mathbb{E}[N])\le1+\log\left(1+\frac{(\rho-1)\sum_{v\in C}\xi_v^{(j)}}{f_j}\right).

Adding the bounds for the three cases gives

E[LC(j)]≤3+log⁡nlog⁡ρ+log⁡(1+(ρ−1)∑v∈Cξv(j)fj).\mathbb{E}[L_C^{(j)}]\le3+\frac{\log n}{\log\rho}+\log\left(1+\frac{(\rho-1)\sum_{v\in C}\xi_v^{(j)}}{f_j}\right).

The proof of Proposition 4.9 immediately follows by applying Claims 4.11 and 4.12 and use Claim 4.10 to obtain ∑v∈Cξv(j)≤2∑v∈Cd(c,v)=2conn⁡(C)\sum_{v\in C}\xi_v^{(j)}\le2\sum_{v\in C}d(c,v)=2\operatorname{conn}(C).

Summing the prices

We now conclude the proof of Theorem 4.1.

Proof of Theorem 4.1. Fix a comparison cluster CC. First, we have that the harmonic bound (9) yields

E[WC]=∑j≤jCfjE[KC(j)]≤HB∑j≤jCfj≤2fCHB.\mathbb{E}[W_C]=\sum_{j\le j_C}f_j\mathbb{E}[K_C^{(j)}]\le H_B\sum_{j\le j_C}f_j\le2f_CH_B.

For the other bound, we first account for the nonregular certifications. If ξv(j)<fj\xi_v^{(j)}<f_j, certification gives qj(Fv+)≤ξv(j)<fjq_j(F_v^+)\le\xi_v^{(j)}<f_j, after which no shifted key above fjf_j can be certified at this level. Thus there is at most one such nonregular certification per level. All other nonregular certifications satisfy fj≤ξv(j)≤2d(c,v)f_j\le\xi_v^{(j)}\le2d(c,v). Since each charge in WCW_C is covered by either a regular or a nonregular certification, the geometric prices give

WC≤∑j≤jCfjLC(j)+∑v∈C∑j≤jCfj≤2d(c,v)fj+∑j≤jCfj≤∑j≤jCfjLC(j)+4conn⁡(C)+2fC.W_C\le\sum_{j\le j_C}f_jL_C^{(j)}+\sum_{v\in C}\sum_{\substack{j\le j_C\\f_j\le2d(c,v)}}f_j+\sum_{j\le j_C}f_j\le\sum_{j\le j_C}f_jL_C^{(j)}+4\operatorname{conn}(C)+2f_C.

Moreover, setting ρ=exp⁡(max⁡{1,log⁡(n+1)})\rho=\exp\left(\max\left\{1,\sqrt{\log(n+1)}\right\}\right) and using log⁡(1+x)≤x\log(1+x)\le x,

log⁡(1+2(ρ−1)conn⁡(C)fj)≤log⁡(ρfCfj(1+2conn⁡(C)fC))≤max⁡{1,log⁡(n+1)}+log⁡fCfj+2conn⁡(C)fC,\begin{aligned} \log\left(1+\frac{2(\rho-1)\operatorname{conn}(C)}{f_j}\right)\le\log\left(\rho\frac{f_C}{f_j}\left(1+\frac{2\operatorname{conn}(C)}{f_C}\right)\right) \\ &\le\max\left\{1,\sqrt{\log(n+1)}\right\}+\log\frac{f_C}{f_j}+\frac{2\operatorname{conn}(C)}{f_C}, \end{aligned}

since fj≤fCf_j \le f_C. Finally, since opening costs are rounded to powers of two, they satisfy ∑j≤jCfj<2fC\sum_{j \le j_C} f_j < 2f_C and ∑j≤jCfjlog⁡(fC/fj)≤fClog⁡2∑k≥0k2−k=2fClog⁡2\sum_{j \le j_C} f_j \log(f_C/f_j) \le f_C \log2 \sum_{k \ge0} k2^{-k} = 2f_C \log2. Substituting all of the above three these inequalities into (10) gives

E[WC]≤4conn⁡(C)+2fC+∑j≤jCfjE[LC(j)]\mathbb{E}[W_C] \le4\operatorname{conn}(C) + 2f_C + \sum_{j \le j_C} f_j\mathbb{E}[L_C^{(j)}]
≤8conn⁡(C)+2fC(4+log⁡nmax⁡{1,log⁡(n+1)}+max⁡{1,log⁡(n+1)}+log⁡2)\le8\operatorname{conn}(C) + 2f_C\left(4 + \frac{\log n}{\max\{1,\sqrt{\log(n+1)}\}} + \max\{1,\sqrt{\log(n+1)}\} + \log2\right)
≤8conn⁡(C)+16max⁡{1,log⁡(n+1)}fC.\le8\operatorname{conn}(C) + 16\max\{1,\sqrt{\log(n+1)}\}f_C.

Applying Proposition 4.8, summing over the optimal clusters, and using ∑CfC<2OPTopen\sum_C f_C < 2\mathrm{OPT}_{\mathrm{open}}, we obtain

E[ALG]≤∑C(34conn⁡(C)+12E[WC])\mathbb{E}[\mathrm{ALG}] \le\sum_C \left(34\operatorname{conn}(C) + 12\mathbb{E}[W_C]\right)
≤130OPTconn+48min⁡{HB,8max⁡{1,log⁡(n+1)}}OPTopen,\le130\mathrm{OPT}_{\mathrm{conn}} + 48\min\{H_B,8\max\{1,\sqrt{\log(n+1)}\}\}\mathrm{OPT}_{\mathrm{open}},

which proves the first assertion. For the second assertion, we use the two-copy algorithm of Observation 2.2. On the one hand, the singleton copy has the same law as one shuffled batch, so the bound with B=1B=1 applies. On the other hand, The nonsingleton copy has at most 2(n−B)2(n-B) clients and BB batches. We, thus, apply the preceding cluster bound to both copies, using the same optimal solution restricted to their clients. Their connection costs add to OPTconn\mathrm{OPT}_{\mathrm{conn}}, and each opening cost is counted at most twice, so

E[ALGcombined]≤O(1)OPTconn+O(min⁡{log⁡(B+1),log⁡(n−B+2)})OPTopen,\mathbb{E}[\mathrm{ALG}_{\mathrm{combined}}] \le O(1)\mathrm{OPT}_{\mathrm{conn}} + O\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right)\mathrm{OPT}_{\mathrm{open}},

proving the second assertion.

Lower bounds

We use Fotakis’s binary-tree construction [5], with more batches at shallower depths so that random batch order still reveals many successively deeper vertices. All opening costs are one, and facilities may be opened at any vertex of the known tree. The bounds hold even if each arriving batch is revealed in full and all batch sizes are known in advance.

Lemma 5.1 (Charging changes of the deepest revealed vertex). Choose a uniform root-to-leaf path in a complete binary metric tree. Each block consists of clients at one path vertex; block sizes, depths, and order are independent of the path. Suppose each nonroot block’s size times its parent-edge length is at least one. If RR vertices are deeper than every previously revealed vertex, counting the first reveal, then E[ALG]≥E[R]/3\mathbb{E}[\mathrm{ALG}] \ge\mathbb{E}[R]/3. The block depths and any hierarchy independent of the path may be known in advance.

Proof. Call these vertices records, and write TvT_v for the subtree rooted at vv. Fix the block order and the algorithm’s randomness. Consider consecutive records vav_a, vbv_b, at depths a<ba < b, just before vbv_b is revealed. If no facility is open in TvaT_{v_a}, serving the earlier block at vav_a cost at least one in connections across its parent edge. This case is impossible when vav_a is the root, since a facility must already be open. Otherwise, choose one open facility in TvaT_{v_a}. Conditional on the history, vbv_b is uniform among its 2b−a2^{b-a} possible descendants: earlier clients reveal no path vertex below vav_a. Thus the chosen facility lies outside TvbT_{v_b} with probability at least 1/21/2; charge its opening on this event.

No cost is charged twice: each record block is used once, and an excluded facility lies outside every later record’s subtree. Consequently E[ALG]≥(E[R]−1)/2\mathbb{E}[\mathrm{ALG}] \ge(\mathbb{E}[R]-1)/2. Together with ALG≥1\mathrm{ALG} \ge1, this gives E[ALG]≥E[R]/3\mathbb{E}[\mathrm{ALG}] \ge\mathbb{E}[R]/3.

Lemma 5.2 (A hard batched instance). For every integer h≥4h \ge4, there is a distribution with Bh=2h+1−1B_h = 2^{h+1}-1 batches and nh−Bh=exp⁡(Θ(h2))n_h-B_h = \exp(\Theta(h^2)) such that E[ALG]≥(h+1)/6\mathbb{E}[\mathrm{ALG}] \ge(h+1)/6 and OPT≤5/4\mathrm{OPT} \le5/4.

Proof. In Fotakis’s notation, take a complete binary tree TT of height hh, with edge length D/miD/m^i from depth ii to i+1i+1. Set m=2h+3m=2^{h+3} and D=1/mD=1/m, and choose a uniform path v0,…,vhv_0,\ldots,v_h. At viv_i, put 2h−i2^{h-i} batches, each containing mim^i clients. Opening only at vhv_h gives

OPT≤1+∑i=0h−12h−imi∑ℓ=ih−1Dmℓ≤1+2h+1−2m−1<54.\mathrm{OPT} \le1+\sum_{i=0}^{h-1}2^{h-i}m^i\sum_{\ell=i}^{h-1}\frac{D}{m^\ell}\le1+\frac{2^{h+1}-2}{m-1}<\frac{5}{4}.

For every nonroot batch, its size times its parent-edge length is miD/mi−1=mD=1m^iD/m^{i-1}=mD=1. Moreover, viv_i is a record exactly when one of its batches precedes every deeper batch. Hence

P(vi is a record)=2h−i∑ℓ=ih2h−ℓ≥12,E[ALG]≥E[R]3≥h+16,\mathbb{P}(v_i\text{ is a record})=\frac{2^{h-i}}{\sum_{\ell=i}^{h}2^{h-\ell}}\ge\frac{1}{2},\qquad\mathbb{E}[\mathrm{ALG}]\ge\frac{\mathbb{E}[R]}{3}\ge\frac{h+1}{6},

where we apply Lemma 5.1. Finally,

Bh=∑i=0h2h−i=2h+1−1,mh≤nh=∑i=0h2h−imi<2mh.B_h=\sum_{i=0}^{h}2^{h-i}=2^{h+1}-1,\qquad m^h\le n_h=\sum_{i=0}^{h}2^{h-i}m^i<2m^h.

Since log⁡m=Θ(h)\log m=\Theta(h), these formulas give log⁡(nh−Bh)=Θ(h2)\log(n_h-B_h)=\Theta(h^2).

Theorem 5.3 (Batched lower bound for every nn and BB). For every n≥1n\ge1 and 1≤B≤n1\le B\le n, every randomized algorithm has competitive ratio at least

Ω(min⁡{log⁡(B+1),log⁡(n−B+2)}).\Omega\left(\min\left\{\log(B+1),\sqrt{\log(n-B+2)}\right\}\right).

This holds with uniform costs, and therefore also with nonuniform costs, even if each arriving batch is revealed in full.

Proof. The construction must fit both the batch budget BB and the excess-client budget n−Bn-B, and thus choose

h=⌊12min⁡{log⁡2(B+1),log⁡2(n−B+2)}⌋.(13)h=\left\lfloor\frac{1}{2}\min\left\{\log_2(B+1),\sqrt{\log_2(n-B+2)}\right\}\right\rfloor. \tag*{(13)}

If h<4h < 4, the claimed factor is constant and follows from ALG≥OPT\mathrm{ALG} \ge\mathrm{OPT}. Otherwise, the preceding construction satisfies

Bh≤22h−1≤B,nh−Bh<2mh≤22h2≤n−B+2≤n−B.B_h \le2^{2h} - 1 \le B,\qquad n_h - B_h < 2m^h \le2^{2h^2} \le\sqrt{n - B + 2} \le n - B.

Here 2mh=21+h(h+3)≤22h22m^h = 2^{1+h(h+3)} \le2^{2h^2} for h≥4h \ge4. Add B−BhB - B_h singleton batches at the root, and add (n−B)−(nh−Bh)(n - B) - (n_h - B_h) clients to an existing root batch. This gives exactly nn clients and BB batches. Opening also at the root keeps OPT≤9/4\mathrm{OPT} \le9/4.

The added clients reveal nothing about the path. The original batches retain their uniform relative order, so all their nonroot records remain records, giving E[R]≥h/2E[R] \ge h/2. The hypothesis of Lemma 5.1 is unchanged, and thus E[ALG]≥h/6E[\mathrm{ALG}] \ge h/6. Averaging over the hidden path yields a fixed instance with expected ratio Ω(h)\Omega(h) for any randomized algorithm.

Acknowledgments

Fabrizio Grandoni is partially supported by the SNF Grants 200021-200731 and 200021-236706. Stefano Leonardi is partially supported by AI-PHOQUS PN RIC 2021-2027, co-financed by EU Italian Ministry MIMIT and MUR. The authors thank Anupam Gupta and Michał Pawłowski for fruitful discussions in the early stages of this work. The authors also acknowledge using GPT-5.6 and GPT-6 Pro in developing this work, specifically to investigate proof strategies and support verification. The authors take full responsibility for the content of this work.

References

  1. [1]Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jarosław Byrka, Fabrizio Grandoni, Krzysztof Sornat, and Antoine Tinguely. An O(log log n)-approximation for submodular facility location. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
  2. [2]Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6:1–6:33, 2013.DOI
  3. [3]Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 940–986. SIAM, 2023.
  4. [4]Dimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis, Nikolas Patris, and Thanos Tolias. Improved bounds for online facility location with predictions. Proceedings of the AAAI Conference on Artificial Intelligence, 39(25):26973–26981, 2025.
  5. [5]Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1–57, 2008.
  6. [6]Anupam Gupta, Gregory Kehne, and Roie Levin. Random order online set cover is as easy as offline. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), pages 1253–1264. IEEE, 2022.DOI
  7. [7]Anupam Gupta, Gregory Kehne, and Roie Levin. Set covering with our eyes wide shut. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4530–4553. SIAM, 2024.arxiv.org/abs/2304.02063
  8. [8]Anupam Gupta, Marco Molinaro, and Matteo Russo. A learning perspective on random-order covering problems. In Proceedings of the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 444–462. SIAM, 2026.arxiv.org/abs/2511.07283
  9. [9]Anupam Gupta and Sahil Singla. Random-order models. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 234–258. Cambridge University Press, 2021.arxiv.org/abs/2002.12159
  10. [10]Yichen Huang and Shaofeng H.-C. Jiang. The power of arrival times in random-order online facility location. arXiv:2607.10564, 2026.arxiv.org/abs/2607.10564
  11. [11]Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In International Conference on Learning Representations (ICLR), 2022.arxiv.org/abs/2110.08840
  12. [12]Haim Kaplan, David Naori, and Danny Raz. Almost tight bounds for online facility location in the random-order model. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1523–1544. SIAM, 2023.arxiv.org/abs/2207.08783
  13. [13]Harry Lang. Online facility location against a t-bounded adversary. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1002–1014. SIAM, 2018.DOI
  14. [14]Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58, 2013.
  15. [16]Stefano Leonardi and Guido Schäfer. Cross-monotonic cost sharing methods for connected facility location games. Theoretical Computer Science, 326(1–3):431–442, 2004.
  16. [17]Adam Meyerson. Online facility location. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 426–431. IEEE, 2001.DOI
  17. [18]Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, 36(2):411–432, 2006.DOI
  18. [20]David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pages 265–274. ACM, 1997.

Paper details

vlnc:W_bpangt7j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 13

downloads · 2

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

  • Computer Science

GPT-5.6, GPT-6 Pro

View statement
Looking for related papers…
Contents