betaFeedback

WorksComputer Science

Capacitated Line Aggregation with Maximum Delay

Abstract

We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most gg requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio 36+12336+12\sqrt3. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to (18+63)/ln⁡2(18+6\sqrt3)/\ln2 against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows (1+ε)(1+ε)-consistency against every complete feasible advice schedule and O(ε−2)O(ε^{-2})-robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost. Controlled synthetic experiments with 9,180 exact-rational monitor runs illustrate both the benefit of optimal advice and the delayed fallback caused by the stated conservative constants. We provide all inputs, outcomes, and reproducibility code; the experiments do not claim performance on learned predictions or large-scale demand traces.

Introduction

Sending an acknowledgment, replenishing several types of goods, and serving requests along a common route all allow several requests to share one service cost. Waiting for more requests can reduce that cost, but also delays the requests already present. This tradeoff has been studied in TCP acknowledgment [12, 33, 18], joint replenishment (JRP) [1, 15, 16, 10, 5], and control-message aggregation [19, 8, 6]. Multi-level aggregation (MLA) extends these problems to rooted trees, with algorithms for additive waiting costs and deadlines [3, 4, 9, 2, 28, 22] and a stochastic-arrival variant [27].

Under per-batch maximum delay, each service pays its service cost plus the waiting time of its oldest request, and the objective sums these costs over all services. Lu et al. Lu et al. [26] study this objective for uncapacitated multi-level aggregation on rooted trees. They obtain optimal competitive ratios of 2 deterministically and e/(e−1)e/(e-1) against an oblivious adversary. We study what happens when a capacity constraint is added, focusing on line aggregation with delay (LAD).

In capacitated LAD, requests arrive at locations on a rooted half-line. Each service completes at most gg pending requests and pays the distance to the farthest one, together with their maximum waiting time. Besides choosing when to serve, the algorithm must choose which requests to serve together. Even on a line, these decisions are closely coupled: a distant request can pay for serving nearby requests, but each nearby request occupies a place that a later request might use.

Under additive delay, every pending request contributes to the waiting cost. Under maximum delay, younger requests can join a batch without increasing its waiting cost. This sharing is useful only while the requests fit. If an uncapacitated service is split into several feasible batches, several of them may contain old requests, and each batch pays its own maximum waiting time. Conversely, serving each distance class independently avoids this splitting decision but loses opportunities to share waiting across classes. For LAD, this gives a logarithmic competitive ratio; see § 3.1 for the algorithm and a matching lower-bound instance.

For LAD, we avoid this logarithmic loss by combining requests across distance classes and obtain a constant-competitive online algorithm. The algorithm assigns requests to future batches through nested time intervals. Its admission rule controls both the capacity of a batch and the cost of opening a new batch when admission fails. Thus capacity does not force the logarithmic loss incurred by independent distance classes.

Our contributions. We obtain the following main results in this paper.

  • For LAD, we give a deterministic online algorithm with competitive ratio 36+123<56.78536+12\sqrt{3}<56.785 for capacity gg. For radii on a fixed scaled dyadic grid, the competitive ratio is 18+6318+6\sqrt{3}. A random common scale offset gives an expected competitive ratio of (18+63)/ln⁡2<40.962(18+6\sqrt{3})/\ln2<40.962 against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes, as described in § 3.5.

  • We also study capacitated LAD in the learning-augmented model. An algorithm receives advice only when a proposed service is due. We combine this advice with any deterministic RR-competitive baseline. For 0<ε≤10<\varepsilon\le1, the resulting algorithm is (1+ε)(1+\varepsilon)-consistent against every complete feasible advice stream and (32/ε2+72/ε+36)R(32/\varepsilon^2+72/\varepsilon+36)R-robust. Our LAD baseline gives O(ε−2)O(\varepsilon^{-2})-robustness.

  • We evaluate the stated advice monitor on 60 synthetic 12-request instances, three capacities, and two feasible advice-corruption mechanisms, giving 9,180 exact-rational runs. Exact offline optima and an independent schedule evaluator support the cost comparisons. Optimal advice attains the optimum on these tests, while conservative switching can make poor advice substantially more expensive than the no-advice baseline. We retain all outcomes and provide the full data and code

in the ancillary material; § 5 and Appendix § 16 describe the protocol and its limitations.

At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of e/(e−1)e/(e-1) on competitive ratios uniform in capacity. Appendix § 8 gives the fixed-location algorithm and both lower-bound arguments.

Our techniques. Our algorithms address two difficulties: assigning requests to future batches and switching between schedules that have served different requests.

  • A constant-competitive algorithm. We use Next Fit along paths of nested time intervals. A path-load test accounts for group sizes and interval lengths, ensuring capacity and paying for new batches when admission fails. Next Fit prevents descendants from repeatedly charging the same ancestor. § 3.2 develops the rule and its additive charges through a worked example.

  • Online advice. Switching schedules requires clearing requests that the new schedule may already have served. We separate the service and waiting costs of this clearance. Baseline budgets control service costs; successive decreases in the remaining advice cost pay waiting charges across switches without repeatedly charging an entire advice batch.

Related work

Aggregation with additive waiting and maximum delay. TCP acknowledgment, JRP, control-message aggregation, and MLA have been studied with additive waiting costs and deadlines [12, 18, 10, 5, 6, 3, 4, 9, 2, 28, 22]. Our direct predecessor is the work of Lu et al. [26] on uncapacitated aggregation with per-batch maximum delay. They show that an offline optimum serves consecutive arrival blocks. This yields a polynomial-time offline dynamic program, which also sets the deadlines of their online algorithm. With capacity, such a block may not fit in one service, and splitting it can charge the same waiting period to several batches.

Lu et al. [24] extend the maximum-delay framework to monotone subadditive service costs. With exact batch optimization, they obtain optimal competitive ratios of 2 deterministically and e/(e−1)e/(e-1) randomly against an oblivious adversary. Their framework requires every request set to be realizable by one service. In LAD, f(Q)=max⁡r∈Qxrf(Q)=\max_{r\in Q}x_r remains subadditive, but the union of two capacity-feasible batches need not fit in one service. Treating their partition as a single service would omit the separate maximum-delay charges, so this framework does not directly apply.

Capacitated batching and capacity transfer. Lu et al. [23] study bin packing with per-bin maximum delay and arbitrary positive item sizes. This is the single-location special case of our size extension, with unit service cost. They obtain an expected competitive ratio of approximately 2.418 against an oblivious adversary in the ideal random-real model. Our setting allows requests at different distances to share a service.

Offline capacitated LAD with deadlines is captured by Nonner’s [30] capacitated max-batching model. A request with window [ar,br][a_r,b_r] and radius xrx_r corresponds to an interval of weight xrx_r. A feasible batch contains at most gg intervals with a common intersection and costs their maximum weight. The problem is strongly NP-hard already for g=3g=3 and admits a PTAS for every fixed gg. For proper interval graphs, Correa and Megow [11] give a PTAS with arbitrary capacity. These results concern deadline feasibility and service cost, rather than per-batch maximum delay.

A different connection concerns adding capacity to an uncapacitated schedule. Tour-partitioning bounds combine an uncapacitated service cost with a demand-weighted root-distance lower bound [7, 36]. Fukunaga et al. [14] use a reduction from capacitated to uncapacitated periodic inventory routing, where costs include inventory holding. For aggregation, splitting a service at its original time preserves additive waiting costs and deadline feasibility. Applying the partitioning bounds and a volume lower bound therefore increases the competitive ratio by only an additive constant; we give the derivation in Appendix § 10. This argument does not extend to maximum delay, since each resulting batch pays its own maximum waiting time.

Dynamic bin packing and busy-time scheduling. MinUsageTime dynamic bin packing and busy-time scheduling group items or jobs under capacity constraints and charge the total time for which bins or machines are used [20, 17, 21, 35, 32, 13, 34, 29, 31]. There is a temporal resemblance to our objective: the maximum waiting time of a batch is the length of the union of its requests’ waiting intervals. In LAD, however, these intervals all end at a common service time chosen by the algorithm. Capacity bounds the total number of requests in the batch. In dynamic bin packing, departures free capacity that later arrivals can reuse. Thus the shared busy-time interpretation does not by itself transfer algorithms or lower bounds to LAD, which also charges a distance-dependent service cost.

Learning-augmented LAD. Lu et al. [25] study uncapacitated LAD with additive waiting costs, including deterministic and randomized learning-augmented algorithms using online suggestions of service lengths. We follow their consistency benchmark of any feasible advised schedule. With capacity, our advice also specifies which requests a service completes. It is revealed only at the proposed service time. Our analysis must account for requests that remain pending when the algorithm switches schedules, even if the schedule it starts following has already served them. § 4 gives the switching rule and the residual-advice argument that controls these costs.

Organization. § 2 introduces the model. § 3 develops the constant-competitive LAD algorithm, from the failure of independent distance classes to the Next Fit construction, its analysis, and the arbitrary-size extension. § 4 gives the online-advice algorithm and the route to its consistency and robustness bounds. The appendices contain the fixed-location results, the baseline upper bound, capacity transfer, the detailed path-load and advice proofs, and the arbitrary-size extension.

Preliminaries

In LAD, each request rr has an arrival time ar≥0a_r \ge0 and a distance xr≥0x_r \ge0 from the origin on a rooted half-line, both revealed at arrival. We call xrx_r its radius. Requests remain distinct even when they arrive at the same location and time. The capacity is a known integer g≥1g \ge1. A service (Q,t)(Q,t) completes a nonempty set QQ of at most gg pending requests at time tt. Its service and total costs are

f(Q)=max⁡r∈Qxr,c(Q,t)=f(Q)+max⁡r∈Q(t−ar).(1)f(Q) = \max_{r \in Q} x_r, \qquad c(Q,t) = f(Q) + \max_{r \in Q}(t-a_r). \tag*{(1)}

The objective is to minimize the sum of these costs. Each request must be served exactly once. Services are instantaneous, and several separately paid batches may be served at the same time. Capacity is shared across all locations in a batch; a completed batch cannot accept later requests. At one location, LAD is capacitated TCP acknowledgment.

Inputs are finite, but their number of requests and end time are not announced. All arrivals at a timestamp are revealed before services at that time. An online algorithm uses only the revealed history and must eventually serve every request. We write ALG⁡(I)\operatorname{ALG}(I) for its total cost on input II and OPT⁡(I)\operatorname{OPT}(I) for the minimum cost of a feasible offline schedule. A deterministic algorithm is RR-competitive if ALG⁡(I)≤ROPT⁡(I)\operatorname{ALG}(I) \le R\operatorname{OPT}(I) for every input, with no additive constant. Unless stated otherwise, we assume g≥2g \ge2 and positive radii: for g=1g = 1, immediate singleton service is optimal, and zero-radius requests can always be served immediately for free. § 3.5 extends the model to arbitrary indivisible request sizes.

An O(1)-competitive algorithm for LAD

Capacity makes the uncapacitated maximum-delay algorithm unusable in two different ways. A pending block may contain more than gg requests, and splitting it can charge the same waiting period to several batches. Serving each radius class separately avoids this split, but loses the waiting-cost sharing between classes. We first isolate that loss and then give the constant-competitive algorithm.

Why separate radius classes lose a logarithmic factor

Round each positive radius upward to a power of two. At every rounded radius yy, independently serve the gg oldest requests when gg are pending, and otherwise serve all pending requests when the oldest reaches age yy.

Proposition 3.1. For g≥2g \ge2, this independent-class algorithm is O(log⁡g)O(\log g)-competitive.

Appendix § 9 gives the proof. The following instance shows that the loss is intrinsic to separating the classes.

Let m=⌊log⁡2(g+1)⌋m = \lfloor\log_2(g + 1) \rfloor and R=2m−1R = 2^{m-1}. For i=0,…,m−1i = 0, \ldots, m - 1, release one request at radius 2i2^i at every time 2j2i2^j2^i, where j=0,…,R/2i−1j = 0, \ldots, R/2^i - 1. There are ∑iR/2i=2m−1≤g\sum_i R/2^i = 2^m - 1 \le g requests in total. The class algorithm serves each request alone and pays 2R2R per class, hence 2mR2mR altogether. Offline serves all requests in one batch at the last arrival and pays 3R−23R - 2. The competitive ratio is therefore Ω(log⁡g)\Omega(\log g) even though the entire input fits in one batch. The lost factor comes from repeatedly paying waiting cost that one shared batch pays once.

Next Fit along nested time intervals

We now let radius classes share future batches. For the moment suppose that radii are powers of two. For each radius yy and each multiple bb of yy, collect the requests that arrived in [b−y,b)[b-y,b). At time bb, serve full groups of gg immediately and retain the remaining requests as one cohort. Give this cohort the home interval [b,b+y)[b,b+y). These homes are nested or disjoint.

A selected home is a root and represents one future batch, served at its right endpoint. A cohort may join the nearest selected root containing its home. Suppose that the candidate root has width RR, while the cohort has MM requests and home width yy. The cohort contributes the constant load

MRgy=MgRy(2)\frac{MR}{gy} = \frac{M}{g}\frac{R}{y} \tag*{(2)}

on its home. The first factor records capacity use; the second records how long the candidate owner keeps that capacity. The cohort joins the root only if the total load on its home remains at most one. Otherwise it opens a new root. Later descendants test this new root rather than returning to older ancestors. This is Next Fit along each path of nested homes.

The load test already implies capacity feasibility. The integral of the load assigned to a root of width RR is R/gR/g per request and is at most RR. Hence at most gg requests join the root. Every assigned request has radius at most RR and waits at most 2R2R, so the resulting batch costs at most 3R3R.

A worked example. Let g=8g = 8. Two requests of radius 88 arrive at time 00; two requests of radius 44 arrive at time 44; and at time 88 one request of radius 22 and one of radius 44 arrive. Figure 1 follows the six requests.

Cohort homes, assigned batches, and final load of the root

Figure 1. The six-request example from § 3.2. The radius-8 requests arrive at time 0, the first radius-4 pair at time 4, and the other two requests at time 8. A home starts when its cohort becomes available for assignment, rather than at the requests’ actual arrival. The orange cohort is rejected at time 10 and served at time 12 for cost 6; the five blue requests are served at time 16 for cost 24. A feasible offline batch at time 8 costs 16. Disjoint homes use different portions of the root’s load budget; only accepted cohorts contribute to the plotted load.

At time 88, the radius-88 cohort opens the root [8,16)[8,16) with load 1/41/4. The radius-44 cohort with home [8,12)[8,12) contributes 1/21/2 and joins it. At time 1010, the radius-22 request reveals home [10,12)[10,12) and would contribute 1/21/2, taking the load there to 5/45/4. It therefore opens a new root and is served at time 1212, for cost 66. At time 1212, the final radius-44 request reveals home [12,16)[12,16). This home is disjoint from [8,12)[8,12), so its test sees load 1/21/2 and it joins the first root. That root serves five requests at time 1616, for cost 2424. The algorithm pays 3030, while one offline batch at time 88 costs 1616.

The rejection at [10,12)[10,12) leaves a capacity slot unused, but it also gives a lower-bound certificate. Either the incoming cohort contributes a constant load, or the old load is already large throughout its home. In the second case, the area under that old load pays for the new root. Next Fit is important here: the first rejected descendant becomes the owner for later descendants, so smaller roots do not repeatedly charge the same area.

The algorithm and its guarantee

For arbitrary radii, fix a scale λ>0\lambda> 0 and round xrx_r upward to the smallest yr∈{λ2j:j∈Z}y_r \in\{\lambda2^j : j \in\mathbb{Z}\}. Define

br=yr(⌊aryr⌋+1),Hr=[br,br+yr).b_r = y_r\left(\left\lfloor\frac{a_r}{y_r} \right\rfloor+ 1\right), \qquad H_r = [b_r, b_r + y_r).

Thus the cohort with home [b,b+y)[b, b+y) is completely known at time bb from requests arriving in [b−y,b)[b-y,b). Homes with the same left endpoint are processed from larger to smaller. Full groups are served first; a nonempty remainder becomes one cohort.

If cohort vv has MvM_v requests and home IvI_v of width yvy_v, and uu is its nearest selected strict ancestor of width RuR_u, then admitting vv would give load

Lu(v)=∑w assigned to uIv⊆IwMwRugyw+MvRugyv.(3)L_u(v) = \sum_{\substack{w\ \text{assigned to}\ u\\ I_v\subseteq I_w}} \frac{M_wR_u}{gy_w}+\frac{M_vR_u}{gy_v}. \tag*{(3)}

The cohort joins uu if Lu(v)≤1L_u(v)\le1; otherwise it becomes a root. Every root serves its assigned cohorts at the right endpoint of its home. Algorithm 1 gives the event-driven rule.

Algorithm 1 Path-load aggregation for LAD

Require: Capacity gg; one fixed scale λ>0\lambda>0; deterministic tie orders

Use λ=1\lambda=1 for the deterministic version; for Corollary 3.3, draw UU uniformly from [0,1)[0,1) once and set λ=2U\lambda=2^U.

  1. Initially no requests, cohorts, or selected roots are stored.

On arrival of request rr at ara_r:

  1. yr←min⁡{λ2j:λ2j≥xr}y_r\leftarrow\min\{\lambda2^j:\lambda2^j\ge x_r\}; br←yr(⌊ar/yr⌋+1)b_r\leftarrow y_r(\lfloor a_r/y_r\rfloor+1)

  2. Store rr in the cohort with home [br,br+yr)[b_r,b_r+y_r).

At a virtual arrival time bb:

  1. for nonempty homes [b,b+y)[b,b+y) in decreasing yy do

  2. Q←Q\leftarrow the requests stored for this home

  3. while ∣Q∣≥g|Q|\ge g do

  4. Serve the first gg requests of QQ at bb and remove them from QQ.

  5. if Q≠∅Q\ne\varnothing then

  6. Create cohort vv with Iv=[b,b+y)I_v=[b,b+y), yv=yy_v=y, and Mv=∣Q∣M_v=|Q|.

  7. u←u\leftarrow the selected strict ancestor of IvI_v of minimum width, if any

  8. if uu exists then

  9. L←∑w assigned to uIv⊆IwMwRugyw+MvRugyvL\leftarrow\sum_{\substack{w\ \text{assigned to}\ u\\ I_v\subseteq I_w}}\frac{M_wR_u}{gy_w}+\frac{M_vR_u}{gy_v}

  10. if uu exists and L≤1L\le1 then

  11. Assign the entire cohort vv to uu.

  12. else

  13. Select vv as a root, set Rv=yvR_v=y_v, and assign vv to itself.

  14. Schedule its service at b+yvb+y_v.

At the service time bu+Rub_u+R_u of a root uu:

  1. Serve all requests assigned to uu in one batch; retire uu.

Theorem 3.2. There is a deterministic online algorithm for LAD with capacity gg whose competitive ratio is at most 36+123<56.78536+12\sqrt{3}<56.785. For radii on one fixed scaled dyadic grid, the ratio is at most

C∗:=18+63<28.393.C_*:=18+6\sqrt{3}<28.393.

The guarantees also hold for adaptively generated inputs.

Why the analysis is additive

The proof compares request charges inside each batch of an arbitrary offline partition. This is necessary because one offline batch may take parts of several online cohorts. Fix such a batch BB and write

XB=max⁡r∈Bxr,YB=max⁡r∈Byr,DB=max⁡r∈Bar−min⁡r∈Bar.X_B = \max_{r\in B} x_r,\qquad Y_B = \max_{r\in B} y_r,\qquad D_B = \max_{r\in B} a_r-\min_{r\in B} a_r.

Serving BB at its last arrival costs XB+DBX_B+D_B. Let αB\alpha_B be the fraction of its capacity occupied by requests that remain after local preprocessing.

There are three charges. Full preprocessed batches charge at most 4(1−αB)YB4(1-\alpha_B)Y_B inside BB. For each residual request assigned to a root of width RR, give the request weight β=R/g\beta=R/g. This weight records the area reserved for that request. For a threshold θ∈(0,1)\theta\in(0,1), call a new root heavy when its own prospective load in its parent is at least θ\theta; distribute the heavy root’s width over the requests that created it, giving weights γ\gamma.

The proof uses the following three bounds:

∑r∈Bβr≤DB+(2+αB)YB,∑r∈Bγr≤DB+(2+αB/θ)YB(4)\sum_{r\in B}\beta_r \le D_B+(2+\alpha_B)Y_B,\qquad\sum_{r\in B}\gamma_r \le D_B+(2+\alpha_B/\theta)Y_B \tag*{(4)}

and the total width of light roots is at most ∑rβr/(1−θ)\sum_r\beta_r/(1-\theta). The first two inequalities use maximal represented homes. They are disjoint and lie in an interval of length DB+2YBD_B+2Y_B. Capacity pays for the remaining requests. The light-root bound integrates the old load over the disjoint rejected homes of each parent. Appendix § 11 proves these statements and also shows why trying older roots before the nearest root can lose a logarithmic factor in this certificate.

Each root batch costs at most three times its width. Combining the three charges and maximizing over αB∈[0,1]\alpha_B\in[0,1] gives

ALG≤∑B(A(θ)DB+C(θ)YB),A(θ)=3(1+11−θ),C(θ)=3(2+1θ+31−θ).(5)\mathrm{ALG}\le\sum_B\left(A(\theta)D_B+C(\theta)Y_B\right),\qquad A(\theta)=3\left(1+\frac{1}{1-\theta}\right),\qquad C(\theta)=3\left(2+\frac{1}{\theta}+\frac{3}{1-\theta}\right). \tag*{(5)}

At θ=1/(1+3)\theta=1/(1+\sqrt{3}), these coefficients are A=6+3A=6+\sqrt{3} and C=C∗C=C_*. On a scaled dyadic grid, YB=XBY_B=X_B; for arbitrary radii, YB<2XBY_B<2X_B. This proves Theorem 3.2. The threshold appears only in the proof, not in the algorithm.

Corollary 3.3. Against an oblivious adversary, LAD with capacity gg admits a randomized online algorithm with expected competitive ratio

18+63ln⁡2<40.962.\frac{18+6\sqrt{3}}{\ln2}<40.962.

Draw UU uniformly from [0,1)[0,1) and use the common scale λ=2U\lambda=2^U. For a fixed radius xx, its rounded value yU(x)y_U(x) satisfies E[yU(x)]=x/ln⁡2\mathbb{E}[y_U(x)]=x/\ln2. Since the rounding map is monotone, the largest rounded radius in BB is yU(XB)y_U(X_B). Taking expectations in (5) proves the corollary. The input must be fixed independently of UU; the exact continuous scale is interpreted in the ideal random-real model.

Arbitrary request sizes

The same algorithm handles indivisible sizes sr∈[0,K]s_r\in[0,K]. In each cohort, serve requests larger than K/2K/2 separately, apply Next Fit to the others, and keep the final nonempty bin as the residual cohort. Replace MvM_v by its total size and gg by KK in the path load. The integral of that load bounds the assigned size by KK.

Corollary 3.4. The deterministic and randomized guarantees of Theorem 3.2 and Corollary 3.3 hold for arbitrary indivisible request sizes, including zero sizes. Neither algorithm needs a minimum-size assumption or an optimum bin-packing oracle.

Appendix § 14 gives the weighted preprocessing and the complete proof.

Learning-augmented capacitated LAD

We next ask whether a good proposed schedule can improve the online cost without sacrificing the worst-case guarantee. Advice is revealed only when it proposes a service: at time tt, an event specifies a capacity-feasible set of already arrived requests to serve. The algorithm sees neither future events nor the total advice cost. Consistency is measured against every complete feasible advice stream, including one that is not optimal.

The difficulty is not merely deciding when to stop trusting advice. Two schedules that have processed the same arrivals may have served different requests. After a switch, the new schedule may refer to requests that are no longer pending, while requests already served by the new schedule may still be pending physically. Clearing the physical queue restores a common state, but one advice batch may then be split across several clearances. Its maximum waiting cost cannot be charged in full at every switch.

Theorem 4.1. For LAD with capacity gg, let BB be a deterministic RR-competitive online algorithm. For every 0<ε≤10 < \varepsilon\le1, there is a deterministic online algorithm such that

ALG⁡(I)≤(1+ε)cost⁡(ADV⁡),(6)\operatorname{ALG}(I) \le(1+\varepsilon)\operatorname{cost}(\operatorname{ADV}), \tag*{(6)}
ALG⁡(I)≤(32ε2+72ε+36)OPT⁡(I).(7)\operatorname{ALG}(I) \le\left(\frac{32}{\varepsilon^2}+\frac{72}{\varepsilon}+36\right)\operatorname{OPT}(I). \tag*{(7)}

The consistency bound holds for every complete capacity-feasible advice stream revealed at its service times. The robustness bound is independent of advice quality and also holds for incomplete advice. The algorithm has polynomial overhead for rational input and ε\varepsilon whenever BB is polynomially simulable.

Using Theorem 3.2 for BB gives O(ε−2)O(\varepsilon^{-2})-robustness.

Scores and switches

The algorithm continuously simulates the advice schedule AA and the robust baseline BB. For a pending set PP at time tt, let

S(P)=min⁡Π∑G∈Πmax⁡r∈Gxr,D(P,t)=min⁡Π∑G∈Πmax⁡r∈G(t−ar),(8)S(P)=\min_{\Pi}\sum_{G\in\Pi}\max_{r\in G}x_r,\qquad D(P,t)=\min_{\Pi}\sum_{G\in\Pi}\max_{r\in G}(t-a_r), \tag*{(8)}

where each minimum ranges over partitions into groups of at most gg requests. Sorting the requests by decreasing radius computes SS; sorting them by decreasing age computes DD. The two partitions may differ, but S(P)+D(P,t)S(P)+D(P,t) is a lower bound on the cost of clearing PP.

For a virtual schedule X∈{A,B}X\in\{A,B\}, let pX(t)p_X(t) be the cost it has paid and PX(t)P_X(t) its pending set. Its score is

HX(t)=pX(t)+S(PX(t))+D(PX(t),t).(9)H_X(t)=p_X(t)+S(P_X(t))+D(P_X(t),t). \tag*{(9)}

The score is nondecreasing. If XX is complete and feasible, then HX(t)≤cost⁡(X)H_X(t)\le\operatorname{cost}(X): restrict its future services to its current pending requests. Thus the score is both observable online and bounded by the final cost of a valid source.

Set

η=ε2,δ=ε4(3+2/ε).\eta= \frac{\varepsilon}{2}, \qquad\delta= \frac{\varepsilon}{4(3 + 2/\varepsilon)}.

The monitor uses dyadic budget levels b,2b,4b,…b, 2b, 4b, \ldots. At level bb, advice is eligible when HA<bH_A < b, while the baseline is eligible when HB<δbH_B < \delta b. The monitor prefers advice whenever it is eligible. If neither source is eligible, it doubles the level. A change of level without a change of source requires no physical action.

When the active source changes, the algorithm first serves every physically pending request. It then follows services of the new source, restricted to requests that remain physically pending. The cleanup on a return to advice also removes requests that virtual advice served while the baseline was active. Consequently, during an XX block the physical pending set is a subset of PXP_X. Appendix § 12 gives the complete event order and pseudocode, including simultaneous arrivals, services, and score timers.

Two simple packing procedures provide the required cleanups. An ordinary cleanup costs at most

2(S(P)+D(P,t)).(10)2\bigl(S(P) + D(P,t)\bigr). \tag*{(10)}

For any η>0\eta> 0, a biased cleanup costs at most

(1+η)D(P,t)+(1+1/η)S(P).(11)(1+\eta)D(P,t) + (1+1/\eta)S(P). \tag*{(11)}

The monitor uses the biased cleanup when leaving advice, because consistency has only an ε\varepsilon margin for waiting cost. It uses the ordinary cleanup when returning to advice. The smaller baseline budget pays for the latter and for the service-cost part of leaving advice.

The residual-advice charge

The central accounting step pays the waiting part of every exit from advice without reusing an advice batch. Fix the original advice batches (Gj,Tj)(G_j,T_j), and let ZZ be the set of requests already served physically. Define the remaining advice cost

Φ(Z)=∑jc(Gj∖Z,Tj),c(∅,Tj)=0.(12)\Phi(Z) = \sum_j c(G_j \setminus Z,T_j), \qquad c(\varnothing,T_j) = 0. \tag*{(12)}

This is an analysis potential, not future information available to the algorithm. It starts at cost⁡(A)\operatorname{cost}(A) and never increases.

A physical service that follows advice decreases Φ\Phi by its own cost. Suppose instead that the monitor leaves advice at time tt and clears a pending set PP. Every request in PP is still pending in virtual advice. For each affected advice batch, deleting these requests either removes the batch or advances its oldest surviving arrival to at least tt. The decrease in its waiting cost is therefore at least the maximum age of the deleted requests from that batch. Since the affected advice batches form a feasible partition of PP, the total decrease is at least D(P,t)D(P,t). Hence

FA+∑e:A→BD(Pe,te)≤cost⁡(A).(13)F_A + \sum_{e:A\to B} D(P_e,t_e) \le\operatorname{cost}(A). \tag*{(13)}

where FAF_A is the cost of physical services that follow advice. Successive switches use successive decreases of Φ\Phi; none charges the original maximum waiting cost twice.

Completing the two bounds

The remaining accounting is geometric. An advice block ending at level bb pays at most (1+η)b(1+\eta)b for its followed services and waiting cleanup. A baseline block ending at level bb pays at most 2δb2\delta b, including its exit cleanup. Each level is the last level of at most one block of each source. If advice is complete, the levels used by baseline blocks and by exits from advice each sum to at most 2cost⁡(A)2\operatorname{cost}(A). Together with (13), this gives

ALG⁡≤[1+η+2δ(3+1η)]cost⁡(A)=(1+ε)cost⁡(A).\operatorname{ALG} \le\left[1+\eta+2\delta\left(3+\frac{1}{\eta}\right)\right]\operatorname{cost}(A)=(1+\varepsilon)\operatorname{cost}(A).

For robustness, no bound on the advice cost is used. The largest opened level is at most 2cost⁡(B)/δ2\operatorname{cost}(B)/\delta, and all opened levels sum to less than twice that value. Applying the same block bounds gives

ALG⁡≤4[1+ηδ+3+1η]cost⁡(B)=(32ε2+72ε+36)cost⁡(B).\operatorname{ALG} \le4\left[\frac{1+\eta}{\delta}+3+\frac{1}{\eta}\right]\operatorname{cost}(B)=\left(\frac{32}{\varepsilon^2}+\frac{72}{\varepsilon}+36\right)\operatorname{cost}(B).

Since cost⁡(B)≤ROPT⁡\operatorname{cost}(B)\le R\operatorname{OPT}, Theorem 4.1 follows. Appendices § 12 and § 13 prove the cleanup, block, and completion statements used here.

The dependence on ε\varepsilon cannot be removed. Already at one location, a deterministic (1+ε)(1+\varepsilon)-consistent algorithm that is RR-robust on inputs of at most gg requests must satisfy

R≥1+g−11+ε(g−1).R\ge1+\frac{g-1}{1+\varepsilon(g-1)}.

Thus any robustness bound uniform in gg is at least 1+1/ε1+1/\varepsilon; the proof appears in Appendix § 13.

Controlled Advice Experiments

We evaluate the stated monitor, including its unmodified constants, on 60 synthetic request instances of size 12: 20 fixed seeds for each of bursty, spread-out, and mixed-scale arrivals. Testing capacities g∈{2,4,8}g\in\{2,4,8\} gives 180 cases with exact offline optima. An exhaustive subset-partition DP computes OPT⁡\operatorname{OPT}; the experiment driver reveals advice services individually at their proposed times. The monitor never receives future advice. We use ε∈{1/4,1/2,1}\varepsilon\in\{1/4,1/2,1\} and compare with path-load without advice and with directly following feasible advice.

Protocol and measurement. The three families vary arrival density and the range of request radii; the same request instance is reused across capacities and monitor settings. Every input and outcome is retained. We report the mean of per-instance ratios, not a ratio of pooled costs. Pointwise 95% intervals use 2000 stratified bootstrap replicates over instance seeds, keeping the capacity variants of each instance together. The benchmark oracle partitions subsets into batches of size at most gg, each served at its last arrival. Its exponential running time confines this exact-OPT study to small inputs. It is independent of the polynomially simulable online rule. All monitor events and costs use rational arithmetic; a separate evaluator checks the physical schedule for complete, capacity-feasible service and recomputes its total cost.

Systematic lateness. Starting from an optimal schedule with mm batches, shift each proposed service later by ρOPT⁡/m\rho\operatorname{OPT}/m. This preserves its partition and makes ADV⁡/OPT⁡=1+ρ\operatorname{ADV}/\operatorname{OPT}=1+\rho exactly, allowing direct comparison across capacities. The experiment varies this ratio from 1 to 10001 to expose both the consistency and fallback regimes. The large errors are deliberate stress tests, rather than an assumed prediction-error distribution.

Figure 2 shows mean finite-input cost divided by exact OPT. With optimal advice, every monitor attains ratio 1.00, versus 2.69 for the baseline on average. With systematic lateness, the monitor initially follows advice: all three settings still have ratio 11 when ADV / OPT = 11. Its proven thresholds are conservative. At quality 1001, the mean ratios are 602.72, 223.62, and 75.42 for ε=1/4,1/2,1\varepsilon= 1/4, 1/2, 1, respectively, all above the baseline. Smaller ε\varepsilon protects consistency but postpones fallback. The observed leveling at the largest tested errors is consistent with fallback; the universal bound comes from the proof.

Figure 2. Controlled advice evaluation, using all generated instances. (a) Shift every optimal advice batch by ρ OPT/m\rho\,\mathrm{OPT}/m, where mm is its number of batches, so ADV/OPT=1+ρ\mathrm{ADV}/\mathrm{OPT}=1+\rho exactly. (b) Capacity dependence at advice quality 1001. Shading and error bars are pointwise 95% stratified cluster-bootstrap intervals, resampling request-instance seeds within each family and retaining their capacity variants together. Colors identify the same ε\varepsilon in both panels; the dashed black curve is the path-load baseline.

At the same level bb, baseline eligibility uses only b/176b/176, b/56b/56, and b/20b/20 in these settings; advice uses bb.

Feasible partition errors and scope. A separate treatment selects optimal batches, shuffles their requests, and repartitions them into capacity-feasible groups, serving each at its last arrival. The realized advice-to-OPT ratios range from 1 to below 4.053. In this range all three monitors have the same physical cost as following advice and make no nonempty switch. This complements the lateness test, but the two treatments do not isolate error structure at matched quality. The tests establish neither average-case superiority over path-load nor scalability on large demand traces. They isolate the behavior of the stated, untuned monitor and identify switching thresholds as a concrete target for improvement.

Appendix § 16 gives the full protocol, family-wise curves, a separate capacity-feasible repartitioning experiment, and all 9180 exact-rational monitor runs. These controlled schedules isolate advice quality; they are not predictions produced by a trained model.

Conclusion and future directions

The constant competitive ratio for capacitated LAD leaves several questions open. What are the optimal deterministic and randomized competitive ratios? Our bounds show that capacity does not force a logarithmic loss, but a gap remains even against the lower bounds from a single location. For online advice, our robustness is O(ε−2)O(\varepsilon^{-2}), while the deterministic lower bound is Ω(ε−1)\Omega(\varepsilon^{-1}) uniformly in capacity. Closing this gap is another natural question. The controlled advice experiments also expose a practical limitation of the current constants: middle-error inputs can trigger fallback only after paying much more than the baseline. Improving these thresholds while retaining consistency and robustness is a further direction.

Extending the constant guarantee beyond a line is a further direction. Does capacitated JRP with maximum delay admit a constant competitive ratio or a constant approximation ratio? For rooted-tree MLA, how should the competitive ratio depend on capacity and tree depth? The LAD admission rule uses nested intervals to control both capacity and the cost of opening batches. For branching service costs, requests can share some edges while paying separately for others; an extension must account for both forms of cost sharing.

Capacity constraints also merit study in online service and facility-location problems with waiting costs. How does maximum delay interact with capacity that can be reused through an opened facility, rather than assigned to a single instantaneous service?

Declaration of AI Use

Generative AI tools assisted mathematical exploration, proof development, drafting, literature searches, experimental-code preparation, and LaTeX preparation. The authors are responsible for the results, references, code, and final text.

Capacitated TCP acknowledgment with maximum delay

The TCP algorithm below handles the single-location special case of LAD and each distance class in § 3.1. We prove its optimal deterministic competitive ratio of two, followed by the randomized lower bound stated in the introduction.

A 2-competitive algorithm

For a fixed setup cost w>0w > 0, a batch costs ww plus its maximum age. The algorithm keeps pending requests in arrival order. Whenever at least gg are pending, it serves the gg oldest and repeats if necessary. Otherwise, it serves the entire pending set when its oldest request reaches age ww. A full-batch trigger has priority over a simultaneous timer. Every resulting batch costs at most 2w2w. Algorithm 2 records this rule. All services occur at the current event time. A stale timer is replaced whenever its buffer changes.

Algorithm 2 The fixed-location full-or-age rule

  1. function FullOrAge(g,wg, w)

  2. Maintain an arrival-ordered queue QQ.

  3. On an arrival block, append its requests to QQ in a fixed tie order.

  4. while ∣Q∣≥g|Q| \ge g do

  5. &nbsp;&nbsp;&nbsp;&nbsp;Serve and remove the first gg requests.

  6. After arrival actions, if Q≠∅Q \ne\varnothing and its oldest age is at least ww, serve all of QQ and empty it.

  7. Otherwise schedule the nonempty queue’s timer at its oldest arrival plus ww.

  8. A timer serves the entire nonempty queue. If w=0w = 0, serve arrivals immediately.

Lemma A.1 (Greedy short prefixes). For requests at one location, call a batch short if it has at most gg members and arrival span at most ww. The greedy partition into maximal arrival-ordered short prefixes minimizes the number of short batches, even when nonconsecutive groups are allowed.

Proof. Let aa denote the earliest arrival, and let GG denote the first q=min⁡{g,∣{r:ar≤a+w}∣}q = \min\{g, |\{r : a_r \le a + w\}|\} requests in arrival order. In any short partition, the batch QQ containing the first request has ∣Q∣≤q|Q| \le q and all its arrivals in [a,a+w][a, a + w].

For each request z∈Q∖Gz \in Q \setminus G, we choose a distinct request y∈G∖Qy \in G \setminus Q and swap zz into the batch containing yy. There are enough such yy because ∣Q∣≤∣G∣|Q| \le|G|. Requests of GG precede all displaced requests in arrival order. Thus an inserted zz arrives no earlier than the removed yy, and no later than a+wa + w. In a receiving batch with original earliest arrival b≥ab \ge a, the new earliest arrival does not decrease, and every inserted arrival is at most a+w≤b+wa + w \le b + w. Its span remains at most ww and its cardinality does not increase. We move any remaining requests of G∖QG \setminus Q into QQ, deleting them from their old batches. The batch QQ has become exactly GG, and no additional batch has been created. Empty batches are deleted.

We remove GG and repeat this exchange on the remaining instance. Induction shows that the greedy partition uses no more batches than the original one.

Proposition A.2 (TCP upper bound). For capacity gg, full-or-age-ww is 2-competitive for TCP.

Proof. Its batches are exactly the maximal short prefixes: a prefix ends when it reaches cardinality gg or when the first request’s age reaches ww. Boundary arrivals are included before a timer is processed. Let GG denote the number of algorithm batches.

We consider any offline batch of at most gg requests, with arrival span Δ\Delta. Its members are divided into greedy prefixes of span at most ww, without a cardinality restriction; each piece still has at most gg members. If there are h≥2h \ge2 pieces, consecutive first arrivals differ by more than ww, and hence (h−1)w<Δ(h - 1)w < \Delta. For h=1h = 1 the bound hw≤w+Δhw \le w + \Delta is immediate. Thus its pieces satisfy hw≤w+Δhw \le w + \Delta, no larger than that comparison batch’s actual cost. Applying this to all comparison batches gives a feasible short partition with number MM satisfying wM≤cost⁡(SOL)wM \le\operatorname{cost}(\mathrm{SOL}). Lemma A.1 gives G≤MG \le M. Hence ALG≤2wG≤2cost⁡(SOL)\mathrm{ALG} \le2wG \le2\operatorname{cost}(\mathrm{SOL}).

A tight deterministic lower bound

Theorem A.3. For every fixed g≥2g \ge2, every deterministic algorithm for capacitated TCP acknowledgment with maximum delay has competitive ratio at least two.

Proof. We fix setup cost c>0c > 0 and an even integer NN. The adversary releases the first request at a1=0a_1 = 0. After the algorithm serves request ii at tit_i, request i+1i + 1 arrives at ai+1=ti+δia_{i+1} = t_i + \delta_i, where δi>0\delta_i > 0. If the algorithm never serves the unique pending request, the adversary ends the input. Otherwise, we write xi=ti−aix_i = t_i - a_i and Δ=∑i<Nδi\Delta= \sum_{i<N} \delta_i. Every online batch is a singleton, and hence

ALG≥Nc+∑i=1Nxi.\mathrm{ALG} \ge Nc + \sum_{i=1}^{N} x_i.

We compare the algorithm with two offline schedules. The first serves the pairs (1,2)(1,2), (3,4)(3,4), …\ldots, (N−1,N)(N-1,N) at their second arrivals. The second serves requests 1,N1,N singly and serves (2,3)(2,3), (4,5)(4,5), …\ldots, (N−2,N−1)(N-2,N-1) at their second arrivals. Their costs O1,O2O_1,O_2 satisfy

O1+O2=(N+1)c+∑i<Nxi+Δ.O_1 + O_2 = (N+1)c + \sum_{i<N} x_i + \Delta.

Indeed every adjacent arrival gap is charged exactly once, and a pair’s additive waiting and maximum waiting are both that gap. Both schedules use at most two requests per batch. With X=∑i<NxiX = \sum_{i<N} x_i,

ALGOPT≥2(Nc+X+xN)(N+1)c+X+Δ≥2Nc(N+1)c+Δ.\frac{\mathrm{ALG}}{\mathrm{OPT}} \ge\frac{2(Nc + X + x_N)}{(N+1)c + X + \Delta} \ge\frac{2Nc}{(N+1)c + \Delta}.

For fixed NN, make Δ/c\Delta/c arbitrarily small, and then let even NN grow. The resulting ratios approach two. For a deterministic algorithm, these release times can be fixed before presenting the input.

An oblivious randomized lower bound

The fixed-location special case also gives a randomized obstruction for capacitated LAD. The following lower bound concerns pure multiplicative guarantees, as in § 2.

Theorem A.4. For cardinality capacity gg, every randomized online algorithm has ratio at least

g1+(g−1)(1−e−1)\frac{g}{1 + (g-1)(1-e^{-1})}

against an oblivious adversary, already at one location. Consequently a competitive constant uniform in gg is at least e/(e−1)e/(e-1). The same constant lower-bounds the arbitrary-size model.

Proof. We normalize the setup cost to one. When all requests fit together, any algorithm can be normalized causally to clear all pending requests when its simulated original execution serves the oldest pending request. This oldest request has not previously been served by the simulation: otherwise a normalized clearance would already have removed it. The new batch has no larger maximum age than that distinct simulated batch, and costs no more. Other simulated actions can be ignored. This also normalizes offline schedules to consecutive groups.

We write δi=ai+1−ai\delta_i = a_{i+1} - a_i for successive arrival gaps. A normalized algorithm cuts a gap at a timeout ziz_i if no arrival intervenes. A cut contributes 1+zi1 + z_i to its total cost; an uncut gap contributes δi\delta_i. The final contribution is 1+zn1 + z_n. The setup in the final contribution and the setups at cuts count exactly the physical batches, while the remaining terms partition their waiting times. Offline chooses each cut independently, obtaining

OPT=1+∑i<nmin⁡{δi,1}.(14)\mathrm{OPT} = 1 + \sum_{i<n} \min\{\delta_i,1\}. \tag*{(14)}

For the lower bound, the input has n=gn = g requests, starts at zero, and has n−1n-1 independent rate-one exponential arrival gaps. This input distribution is independent of the algorithm’s randomness. Conditional on the past, its prospective no-arrival timeout zz is independent of the next gap GG. For every z∈[0,∞]z \in[0,\infty] the expected gap contribution is

E[min⁡{G,z}]+Pr⁡(G>z)=1.\mathbb{E}[\min\{G,z\}] + \Pr(G > z) = 1.

The final contribution is at least one, and hence E[ALG]≥n\mathbb{E}[\mathrm{ALG}] \ge n, whereas (A.1) gives E[OPT]=1+(n−1)(1−e−1)\mathbb{E}[\mathrm{OPT}] = 1 + (n-1)(1-e^{-1}). A guarantee on every fixed input must also hold after averaging over this independent distribution, proving the displayed ratio. Letting gg grow gives the uniform bound. For arbitrary sizes, nn requests of size 1/n1/n give the same bound as nn grows.

Analysis of the independent-class baseline

Section 3.1 defines the algorithm and gives its matching lower-bound instance. Here we prove the upper bound.

Proof of Proposition 3.1. Fix an offline batch with maximum rounded radius RR and arrival span Δ\Delta. If it contains nxn_x requests of radius xx, its restriction can be served together at its last arrival for at most x+Δx+\Delta, or as singletons at their arrivals for cost nxxn_xx. Each restriction fits in one batch, giving total cost at most

∑x≤Rmin⁡{x+Δ,nxx}≤∑x≤Rx dyadicmin⁡{x+Δ,gx}.\sum_{x\le R}\min\{x+\Delta,n_xx\}\le\sum_{\substack{x\le R\\x\ \mathrm{dyadic}}}\min\{x+\Delta,gx\}.

If Δ=0\Delta=0, this sum is at most 2R2R. Otherwise the radii x≤Δ/gx\le\Delta/g contribute at most 2Δ2\Delta by geometric summation. There are at most ⌈log⁡2g⌉+1\lceil\log_2g\rceil+1 dyadic radii in (Δ/g,Δ](\Delta/g,\Delta], each contributing at most 2Δ2\Delta. Radii x>Δx>\Delta contribute at most ∑x≤R2x≤4R\sum_{x\le R}2x\le4R. The sum is at most (2⌈log⁡2g⌉+4)(R+Δ)(2\lceil\log_2g\rceil+4)(R+\Delta). Applying these restrictions to all offline batches gives a feasible comparison schedule for each class. The factor-two TCP guarantee from Proposition A.2 and the factor-two radius rounding therefore give the claimed competitive ratio. □

Proof of capacity transfer for additive delay and deadlines

We derive the capacity-transfer bounds discussed in § 1.1 for additive waiting costs and deadlines. For a rooted-tree batch BB, let prp_r be the length of request rr's root path. Order requests by a depth-first traversal and cut this order at a uniformly chosen residue modulo gg. An edge used by ne>0n_e>0 requests appears in an expected 1+(ne−1)/g1+(n_e-1)/g pieces. Summing over edges bounds the service cost by

(1−1g)f(B)+1g∑r∈Bpr.\left(1-\frac{1}{g}\right)f(B)+\frac{1}{g}\sum_{r\in B}p_r.

For sizes normalized to capacity one, serve requests larger than 1/21/2 separately. Group the others by their cumulative start positions in shifted intervals of length 1/21/2. Each group fits, and an edge is used by at most 1+2∑r∈Besr1+2\sum_{r\in B_e}s_r groups in expectation, where BeB_e contains its small requests. Large requests cost at most twice their volume charge. The resulting bound is f(B)+2∑r∈Bsrprf(B)+2\sum_{r\in B}s_rp_r. Choosing the cheapest offset makes both constructions deterministic. Only polynomially many candidates are needed: an already feasible batch need not be cut, and otherwise there are g<∣B∣g<|B| unit offsets. For arbitrary sizes, the partition changes only when a shifted boundary crosses a cumulative start position, giving at most ∣B∣|B| breakpoints.

Let SA,DAS_A,D_A be the service and additive waiting costs of the virtual schedule. Set α=1−1/g\alpha=1-1/g and write V=∑rpr/gV=\sum_r p_r/g for capacity gg, or V=∑rsrprV=\sum_r s_rp_r for sizes. Every feasible batch pays at least its volume charge, so V≤S∗V\le S^* for any capacitated comparator with service cost S∗S^* and waiting cost D∗D^*. Keeping all service times therefore gives

ALG⁡≤αSA+DA+VorALG⁡≤SA+DA+2V.\operatorname{ALG}\le\alpha S_A+D_A+V\quad\text{or}\quad\operatorname{ALG}\le S_A+D_A+2V.

respectively. An uncapacitated ratio RR immediately yields competitive ratios R+1R+1 and R+2R+2, respectively. With deadlines, DA=D∗=0D_A=D^*=0, giving (αR+1)S∗(\alpha R+1)S^* for capacity gg. For additive waiting, run the baseline with service costs scaled by α\alpha, whenever it supports this scaling:

ALG⁡≤R(αS∗+D∗)+S∗≤max⁡{R,αR+1}(S∗+D∗).\operatorname{ALG}\le R(\alpha S^*+D^*)+S^*\le\max\{R,\alpha R+1\}(S^*+D^*).

All partitions use only the current virtual batch. A capacity-feasible advised schedule is also a valid comparator, so these inequalities transfer both consistency and robustness.

Detailed analysis of the path-load algorithm

This appendix proves the feasibility and charging statements summarized in § 3. It also explains why the nearest-owner rule is needed by the batchwise certificate.

Strict time rounding and local preprocessing

We write ara_r for the arrival time of request rr and xr>0x_r > 0 for its radius. Each batch contains at most gg requests. For a fixed λ>0\lambda> 0, the radius grid is {λ2j:j∈Z}\{\lambda2^j : j \in\mathbb{Z}\}. The deterministic algorithm uses λ=1\lambda= 1; we keep the scale explicit for the randomized extension. The algorithm rounds xrx_r upward to the smallest grid value yr≥xry_r \ge x_r and gives rr the virtual arrival

br=yr(⌊ar/yr⌋+1).b_r = y_r\left(\left\lfloor a_r/y_r\right\rfloor+ 1\right).

Thus 0<br−ar≤yr0 < b_r - a_r \le y_r. Its home interval is Hr=[br,br+yr)H_r = [b_r, b_r + y_r). Any two home intervals are disjoint or one contains the other. At time bb, the full cohort with home [b,b+y)[b, b+y) consists of the requests of rounded radius yy that actually arrived in [b−y,b)[b-y,b). The cohort is therefore known from the strict past. An arrival at time bb cannot change it, even when arrivals depend on earlier service decisions.

At a cohort’s virtual arrival, the algorithm serves full groups of gg requests in a fixed deterministic order. It retains the remaining requests as one residual cohort, if any remain. Thus every preprocessed batch is full, and each residual cohort fits in one batch (line 7 of Algorithm 1).

Every preprocessed batch at a home of width yy has actual waiting at most yy and radius at most yy. Its cost is at most 2y2y, and hence at most 4y/g4y/g times its cardinality. If PP denotes the set of preprocessed requests, then

ALGpre≤4g∑r∈Pyr.(15)\mathrm{ALG}_{\mathrm{pre}} \le\frac{4}{g}\sum_{r\in P} y_r. \tag*{(15)}

We use the loose factor four so that the same accounting also applies to arbitrary sizes in Appendix § 14. The bound assigns preprocessing cost to individual requests. Later we combine these charges with those of residual requests inside each offline batch, using their shared capacity constraint.

The path-load rule

We write vv for a nonempty residual cohort, Iv=[bv,bv+yv)I_v = [b_v,b_v+y_v) for its home, and MvM_v for its cardinality. The algorithm processes homes with the same left endpoint in decreasing order of width. Some homes are selected as roots, each representing one future batch. Every cohort is assigned as a whole to a selected root containing its home. We call that root the cohort’s owner; these interval roots are distinct from the half-line root at the origin.

When cohort vv arrives, let uu denote its nearest selected strict ancestor, if one exists, and write Ru=yuR_u = y_u. To decide whether vv can join uu, the algorithm distributes a load MvRu/(gyv)M_vR_u/(gy_v) over IvI_v. Its integral is MvRu/gM_vR_u/g, the interval length reserved for these requests. Since earlier homes meeting IvI_v contain it, their contributions are constant throughout IvI_v. Admitting vv would give total load

Lu(v)=∑w already assigned to uIv⊆IwMwRugyw+MvRugyv.(16)L_u(v) = \sum_{\substack{w\ \mathrm{already\ assigned\ to}\ u\\ I_v\subseteq I_w}} \frac{M_wR_u}{gy_w} + \frac{M_vR_u}{gy_v}. \tag*{(16)}

If uu exists and Lu(v)≤1L_u(v) \le1, the algorithm assigns vv to uu. Otherwise, vv becomes a new root and owns its own cohort (lines 14–16 of Algorithm 1). A root uu serves all its assigned requests at time bu+Rub_u+R_u. This service time and all earlier assignments remain fixed.

All information used in (D.2) is available online. An ancestor home is revealed before its descendants, with the specified order handling equal left endpoints. A newly revealed descendant starts strictly before its ancestor’s right endpoint, and hence its selected ancestor has not served. Homes starting at an endpoint are outside the interval ending there; simultaneous arrivals and due services cause no ambiguity.

All tie choices are fixed in advance. Empty cohorts create no events.

Lemma D.1. Every root batch is capacity feasible, and its actual cost is at most 3Ru3R_u. Every residual request is eventually served exactly once.

Proof. We first prove capacity by integrating the load and then bound the waiting time of each assigned request. For the final assignment to root uu, define

fu(t)=∑w assigned to uMwRugyw1Iw(t).f_u(t) = \sum_{w\ \mathrm{assigned\ to}\ u} \frac{M_w R_u}{g y_w} 1_{I_w}(t).

Homes containing a fixed point form a chain and are processed in ancestor order. Every accepted cohort checks the existing chain sum plus its own term. The root’s initial term is Mu/g≤1M_u/g \le1. Once a new selected root appears on the chain, subsequent descendants use that nearer root. Consequently fu(t)≤1f_u(t) \le1 almost everywhere. Integration gives

Rug∣{r:r is assigned to u}∣=∫Iufu(t) dt≤Ru.\frac{R_u}{g} \lvert\{r:r\text{ is assigned to }u\}\rvert= \int_{I_u} f_u(t)\,\mathrm{d}t \le R_u.

which proves feasibility without splitting any request.

If rr has home Iw⊆IuI_w \subseteq I_u, then yw≤Ruy_w \le R_u and bw≥bub_w \ge b_u. Its actual arrival satisfies ar≥bw−yw≥bu−Rua_r \ge b_w-y_w \ge b_u-R_u. At time bu+Rub_u+R_u, its waiting is at most 2Ru2R_u and its radius is at most RuR_u. The root batch therefore costs at most 3Ru3R_u. Every residual cohort has one owner with a finite prescribed service time, proving the last claim. □

The complete event-driven rule is Algorithm 1 in the main text.

Two additive certificates

A rejected cohort opens another batch, whose cost must be compared with the offline solution. We use two request charges. The first records the load already assigned to an owner; it will pay for rejections caused by that load. The second pays for a new root when its own cohort contributes a large load. Each charge is bounded inside an arbitrary offline batch. Summing over the offline partition bounds the total charge, even when the batches’ arrival spans overlap.

We fix any feasible offline partition into batches. Each batch BB can be served at its latest arrival, giving minimum cost XB+DBX_B+D_B, where

XB=max⁡r∈Bxr,YB=max⁡r∈Byr,DB=max⁡r∈Bar−min⁡r∈Bar.X_B = \max_{r\in B} x_r,\qquad Y_B = \max_{r\in B} y_r,\qquad D_B = \max_{r\in B} a_r-\min_{r\in B} a_r.

We also write αB=∣B∖P∣/g∈[0,1]\alpha_B = \lvert B\setminus P\rvert/g \in[0,1] for the fraction of capacity used by residual requests in BB. The number of preprocessed requests in BB is at most g(1−αB)g(1-\alpha_B). All residual homes represented in BB lie inside [min⁡Bar,max⁡Bar+2YB][\min_{B} a_r,\max_{B} a_r+2Y_B]. Thus every disjoint collection of such homes has total length at most DB+2YBD_B+2Y_B. This observation compares virtual homes directly with the original arrival span.

Each residual request assigned to uu receives weight βr=Ru/g\beta_r=R_u/g; preprocessed requests receive weight zero. We write W=∑rβrW=\sum_r\beta_r for their total weight.

Lemma D.2. For every feasible offline batch BB,

∑r∈Bβr≤DB+(2+αB)YB.\sum_{r\in B} \beta_r \le D_B + (2+\alpha_B)Y_B.

Proof. Let Q1,…,QmQ_1,\ldots,Q_m be the inclusion-maximal distinct residual homes represented in BB. They are disjoint, with total length at most DB+2YBD_B+2Y_B. We split the charge according to whether a request’s owner is contained in its maximal home QjQ_j or strictly contains QjQ_j. The first group is bounded by the number of requests in BB; the second will be bounded by integrating load over the disjoint QjQ_j.

Owners of the first kind have width at most YBY_B. Each of their requests therefore has weight at most YB/gY_B/g, and there are at most αBg\alpha_B g residual requests in BB. Their total weight is at most αBYB\alpha_B Y_B.

All requests of the second kind within a given QjQ_j have the same owner. To see this, recall that a containing home is processed before its descendants, including when their left endpoints coincide. Every strict ancestor of QjQ_j was therefore known when QjQ_j was processed. Let uu be its nearest selected strict ancestor, if one exists. A descendant home can be assigned above QjQ_j only to uu: any selected root between that home and uu would instead become its nearest candidate owner. Assignments are never revised, so roots selected later inside QjQ_j do not change earlier owners. If QjQ_j itself is selected, or if uu does not exist, the second group is empty. Otherwise, the weight of this group is at most

∫Qjfu(t) dt≤∣Qj∣.\int_{Q_j} f_u(t)\,\mathrm{d}t \le\lvert Q_j\rvert.

Indeed, integrating the density of a whole assigned home contained in QjQ_j gives exactly its total β\beta weight; selecting only part of that cohort reduces the weight. Summing over jj bounds the second group by DB+2YBD_B+2Y_B. Adding the first group’s αBYB\alpha_B Y_B gives DB+(2+αB)YBD_B+(2+\alpha_B)Y_B, as claimed. □\square

An owner may occur in several offline batches. The comparisons remain additive because each batch sums only its own requests’ β\beta weights; the integral bounds these weights without assigning a new charge to the owner each time.

For the analysis, we fix θ∈(0,1)\theta\in(0,1). A selected root vv is heavy if it has no selected ancestor or, writing uu for its parent selected root, if

MvRugyv≥θ.\frac{M_vR_u}{g y_v}\ge\theta.

All other roots are light. Each request in the cohort that created a heavy root vv receives weight γr=yv/Mv\gamma_r=y_v/M_v; all other requests receive weight zero. Every residual cohort is nonempty, and hence Mv>0M_v>0. The total γ\gamma weight equals the total width of heavy roots.

Lemma D.3. For every feasible offline batch BB,

∑r∈Bγr≤DB+(2+αBθ)YB.\sum_{r\in B}\gamma_r \le D_B+\left(2+\frac{\alpha_B}{\theta}\right)Y_B.

Proof. We split the represented heavy roots into maximal and nonmaximal ones. Disjoint homes bound the first group; the heavy-root inequality bounds the charge per request in the second. The inclusion-maximal heavy-root homes whose own-cohort requests occur in BB are disjoint. Their total length is at most DB+2YBD_B+2Y_B, and their represented γ\gamma weight is at most this length, even when BB contains only part of a cohort.

For a nonmaximal represented heavy root vv, some represented heavy ancestor ww exists. The parent selected root uu of vv lies in IwI_w, and hence Ru≤yw≤YBR_u\le y_w\le Y_B. Its heavy inequality gives

γr=yvMv≤Rugθ≤YBgθ.\gamma_r=\frac{y_v}{M_v}\le\frac{R_u}{g\theta}\le\frac{Y_B}{g\theta}.

There are at most αBg\alpha_B g such requests, so the nonmaximal roots contribute at most αBYB/θ\alpha_B Y_B/\theta. Together with the maximal roots’ contribution DB+2YBD_B+2Y_B, this gives the claimed bound. □\square

Lemma D.4. The sum of the widths of light roots is at most W/(1−θ)W/(1-\theta).

Proof. We charge each light root to the load of its parent over its home. These charges use disjoint intervals for a fixed parent, and different parents use the weights of their own assigned requests. Let vv denote a light immediate child root of uu. Its own prospective term is below θ\theta, but its admission failed. The already assigned ancestor terms therefore sum to more than 1−θ1-\theta. Every such term contributes throughout IvI_v and remains in the final density fuf_u. Thus

∣Iv∣≤11−θ∫Ivfu(t) dt.|I_v| \le\frac{1}{1-\theta}\int_{I_v} f_u(t)\,\mathrm{d}t.

Immediate child-root intervals of uu are disjoint. Summing over light children and parents yields

∑v lightyv≤11−θ∑u∫Iufu(t) dt=11−θ∑rβr.\sum_{v\ \mathrm{light}} y_v \le\frac{1}{1-\theta}\sum_u\int_{I_u} f_u(t)\,\mathrm{d}t = \frac{1}{1-\theta}\sum_r \beta_r.

More explicitly, a request rr assigned to uu pays a light child vv of uu the amount

βr1−θ∣Hr∩Iv∣∣Hr∣.\frac{\beta_r}{1-\theta}\frac{|H_r\cap I_v|}{|H_r|}.

Its total contribution is at most βr/(1−θ)\beta_r/(1-\theta) by disjointness. A grandchild of uu uses the requests assigned to its own parent.

Why Next Fit rather than First Fit?

The baseline in § 3.1 loses a logarithmic factor by processing distance classes independently. Our algorithm combines classes, but the choice of owner also matters for its analysis. Consider a First Fit variant that keeps the same preprocessing and load test, but tries all selected containing roots in decreasing order of width. It joins the first root that passes the test and opens a new root only if all fail. This rule still preserves capacity. The example below shows that its β\beta weights need not satisfy a constant-factor bound within an arbitrary feasible offline batch. It is not a competitive lower bound for First Fit.

A three-level example. Let g=16g=16. At time 8−ε8-\varepsilon, release eight requests at each radius 88, 44, and 22, where 0<ε<1/40<\varepsilon<1/4. At virtual time 88, they create roots with homes [8,16)[8,16), [8,12)[8,12), and [8,10)[8,10). Each starts with load 1/21/2. Every smaller seed cohort is rejected by all larger roots, since its prospective load is at least one before adding the existing load.

Inside Q=[8,9)Q=[8,9), create one request for every home in the following three levels. A request with home [h,h+y)[h,h+y) has radius yy and arrives at h−εh-\varepsilon.

levelhome widthnumber of homesowner widthtotal β\beta
01181/2
11/2241/2
21/4421/2

Table 2.

The first request adds load 8/(16⋅1)=1/28/(16\cdot1)=1/2 to the largest root, filling its load throughout QQ. Each half-width home is therefore rejected there, but adds load 4/(16⋅(1/2))=1/24/(16\cdot(1/2))=1/2 to the next root. The quarter-width homes similarly join the smallest root. Ancestor homes are processed first, so each rejection is already determined when it occurs. Thus requests inside the same maximal home QQ use three different owners strictly above QQ, violating the unique-owner property in Lemma D.2.

An unbounded loss in the certificate. For m≥2m \ge2, take g=2m+1g=2^{m+1}, b=2mb=2^m, and ε=2−m\varepsilon=2^{-m}. Release g/2g/2 seed requests at each radius 2m,2m−1,…,22^m,2^{m-1},\ldots,2 at time b−εb-\varepsilon. They create mm roots starting at bb, each with initial load 1/21/2. Let BB consist of one additional request for each dyadic home in Q=[b,b+1)Q=[b,b+1) at levels ℓ=0,…,m−1\ell=0,\ldots,m-1:

Hℓ,j=[b+j2−ℓ,b+(j+1)2−ℓ),j=0,…,2ℓ−1.H_{\ell,j}=[b+j2^{-\ell},b+(j+1)2^{-\ell}),\qquad j=0,\ldots,2^\ell-1.

Its radius is 2−ℓ2^{-\ell} and its arrival is the left endpoint minus ε\varepsilon. No cohort reaches capacity. As in the three-level example, earlier levels fill each larger root on QQ, while disjoint homes at level ℓ\ell fill the remaining load 1/21/2 of the root of width 2m−ℓ2^{m-\ell}. Each level contributes 2ℓ⋅2m−ℓ/g=1/22^\ell\cdot2^{m-\ell}/g=1/2 to the certificate. Thus

∣B∣=2m−1<g,YB=1,DB=1−2−(m−1),∑r∈Bβr=m/2.|B|=2^m-1<g,\qquad Y_B=1,\qquad D_B=1-2^{-(m-1)},\qquad\sum_{r\in B}\beta_r=m/2.

Serving BB at its last arrival costs YB+DB<2Y_B+D_B<2, so its β\beta weight exceeds its batch cost by Θ(log⁡g)\Theta(\log g). This is a loss in the batchwise certificate, not a competitive lower bound for First Fit: the full input also contains the seed requests, whose offline cost might support a different global accounting. Next Fit’s unique-owner property prevents this accumulation of area charges across scales.

Combining preprocessing and residual costs

Figure 3 illustrates the disjoint areas used in Lemma D.4. The accounting follows ownership: nested selected roots do not repeatedly use one ancestor’s requests.

Figure 3. Why the light-root charge does not repeat down the hierarchy (schematic density). A light child’s own term is below θ\theta, so failed admission certifies fu>1−θf_u > 1-\theta throughout its interval. Immediate child-root intervals are disjoint; the shaded areas therefore use disjoint portions of the unique owner’s density. A grandchild has a different parent and uses that parent’s assigned requests. The parameter θ\theta is used only in the analysis.

We combine three charges: preprocessing, heavy roots, and light roots. By Lemmas D.1–D.4, the last two cost at most 3∑rγr3\sum_r\gamma_r and 3W/(1−θ)3W/(1-\theta), respectively. The factor three comes from the root-batch cost bound 3Ru3R_u. Inside an offline batch BB, preprocessing contributes at most 4(1−αB)YB4(1-\alpha_B)Y_B by (D.1), while the two certificates bound the residual charges. Keeping αB\alpha_B in this calculation accounts for the capacity shared by preprocessed and residual requests. Substituting the certificate bounds, the total cost is at most the sum over offline batches of

3(1+11−θ)DB+[3(2+21−θ)+4+αB(3θ+31−θ−4)]YB.3\left(1+\frac{1}{1-\theta}\right)D_B+\left[3\left(2+\frac{2}{1-\theta}\right)+4+\alpha_B\left(\frac{3}{\theta}+\frac{3}{1-\theta}-4\right)\right]Y_B.

The coefficient of αB\alpha_B is positive. Maximizing over αB∈[0,1]\alpha_B \in[0,1] yields the batchwise comparison

ALG⁡≤∑B(A(θ)DB+C(θ)YB),A(θ)=3(1+11−θ),C(θ)=3(2+1θ+31−θ).(17)\operatorname{ALG}\le\sum_B\left(A(\theta)D_B+C(\theta)Y_B\right),\qquad A(\theta)=3\left(1+\frac{1}{1-\theta}\right),\qquad C(\theta)=3\left(2+\frac{1}{\theta}+\frac{3}{1-\theta}\right). \tag*{(17)}

The capacity constraint in this calculation belongs to the offline batch BB. Its preprocessed and residual requests occupy disjoint portions of that capacity, although the online algorithm may serve them in different batches.

The choice θ=1/(1+3)\theta=1/(1+\sqrt{3}) minimizes C(θ)C(\theta) and gives

A(θ)=6+3,C(θ)=C∗=18+63.A(\theta)=6+\sqrt{3},\qquad C(\theta)=C_\ast=18+6\sqrt{3}.

For already scaled-dyadic radii, YB=XBY_B=X_B, and hence (D.3) proves the C∗C_\ast bound. For arbitrary radii, YB<2XBY_B<2X_B, proving the 2C∗2C_\ast bound of Theorem 3.2. The threshold θ\theta changes only the proof, not any online decision. All comparisons hold for each realized input and each feasible offline partition, which also establishes the claimed adaptive-adversary scope.

Randomizing the scale

Proof of Corollary 3.3. The algorithm draws UU uniformly from [0,1)[0,1) once, sets λ=2U\lambda=2^U, and uses this scaled dyadic grid for both radii and time. For any fixed x>0x>0, its rounded radius is

yU(x)=2U+⌈log⁡2x−U⌉,E[yU(x)]=x∫012z dz=xln⁡2.y_U(x)=2^{U+\lceil\log_2x-U\rceil},\qquad\mathbb{E}[y_U(x)]=x\int_0^1 2^z\,\mathrm{d}z=\frac{x}{\ln2}.

We fix an input independent of UU and an optimal partition of the original requests. The common monotone rounding map gives YB=yU(XB)Y_B=y_U(X_B). Applying (D.3) to this same partition for every UU and taking expectations gives

E[ALG⁡]≤∑B((6+3)DB+C∗ln⁡2XB)≤C∗ln⁡2OPT⁡,\mathbb{E}[\operatorname{ALG}]\le\sum_B\left((6+\sqrt{3})D_B+\frac{C_\ast}{\ln2}X_B\right)\le\frac{C_\ast}{\ln2}\operatorname{OPT},

which proves the corollary by linearity of expectation.

The expectation uses an input fixed independently of the scale. For adaptive inputs, the deterministic 2C∗2C_\ast guarantee still holds for every realized scale. The randomized implementation uses an ideal-real computation model: it samples the common scale exactly and performs arithmetic, comparisons, and rounding on real values exactly. It uses polynomially many such operations. We do not claim a finite-bit implementation of this exact continuous random scale.

The full online-advice monitor

This appendix gives the complete monitor, its residual-advice proof, and the algebra behind the two guarantees stated in Theorem 4.1.

Packing costs and virtual schedules

The algorithm serves radius-zero requests immediately for free and removes them from advice. We therefore assume positive radii below. An input containing only radius-zero requests costs nothing.

Separate packing costs. For a pending set PP at time tt, we write wr(t)=t−arw_r(t)=t-a_r and define

S(P)=min⁡Π∑G∈Πmax⁡r∈Gxr,D(P,t)=min⁡Π∑G∈Πmax⁡r∈Gwr(t).(18)S(P)=\min_{\Pi}\sum_{G\in\Pi}\max_{r\in G}x_r,\qquad D(P,t)=\min_{\Pi}\sum_{G\in\Pi}\max_{r\in G}w_r(t). \tag*{(18)}

where each minimum is over partitions into groups of at most gg requests. The two minimizing partitions may differ: SS ignores waiting, and DD ignores distance. Nevertheless, any feasible partition pays at least S(P)S(P) in service cost and D(P,t)D(P,t) in current waiting cost, so their sum is a lower bound on clearing PP. Both values are zero on the empty set. For nonnegative weights vrv_r, sorting them in nonincreasing order and grouping consecutive gg requests minimizes the sum of group maxima. Indeed, for every z≥0z\ge0 any partition has at least ⌈∣{r:vr>z}∣/g⌉\lceil|\{r:v_r>z\}|/g\rceil groups of maximum weight greater than zz, and the sorted partition attains all these bounds. Integration over zz proves optimality. Thus SS and DD are exactly computable by sorting; they are also monotone under taking subsets.

Lemma E.1. There are polynomial-time procedures that clear PP at time tt with cost at most

2(S(P)+D(P,t)).(19)2\bigl(S(P)+D(P,t)\bigr). \tag*{(19)}

and, for any η>0\eta>0, with cost at most

(1+η)D(P,t)+(1+1/η)S(P).(20)(1+\eta)D(P,t)+(1+1/\eta)S(P). \tag*{(20)}

Every output batch has at most gg requests.

The ordinary procedure sorts requests by nonincreasing max⁡{xr,wr(t)}\max\{x_r,w_r(t)\} and groups consecutive gg requests. The biased procedure separates L={r:xr≤ηwr(t)}L=\{r:x_r\le\eta w_r(t)\} from its complement, sorting LL by nonincreasing age and its complement by nonincreasing radius before packing each separately. We use PackValue for the optimum sorted packing value and Clear for either clearance procedure. Their pseudocode and the proof of Lemma E.1 appear in Appendix § 13.

Two virtual schedules. The algorithm continuously simulates two schedules on the original input: the baseline BB and the advice schedule AA. A revealed advice proposal is executed in the simulation of AA. Neither simulation is restarted at a switch. We call their states virtual, and use physical for the services actually executed by our algorithm. Let pX(t)p_X(t) and PX(t)P_X(t) denote the paid cost and pending set of X∈{A,B}X\in\{A,B\}, respectively. Its score is

HX(t)=pX(t)+S(PX(t))+D(PX(t),t).(21)H_X(t)=p_X(t)+S(P_X(t))+D(P_X(t),t). \tag*{(21)}

The score includes both the cost already paid by the virtual schedule and lower bounds on the cost of its pending requests. All three terms are available online. For malformed advice, the algorithm discards identifiers outside PAP_A and ignores empty or capacity-infeasible proposals. This leaves feasible advice unchanged. Physical services leave both virtual pending sets unchanged.

Lemma E.2. The score HXH_X is nondecreasing. If XX is complete and feasible, then HX(t)≤CX:=cost⁡(X)H_X(t)\le C_X:=\operatorname{cost}(X) for all tt. Moreover, for any set PP of already arrived requests,

S(P)≤pB(t)+S(PB(t))≤HB(t).(22)S(P)\le p_B(t)+S(P_B(t))\le H_B(t). \tag*{(22)}

The switching rule

We set

η=ε2,δ=ε4(3+2/ε).(23)\eta= \frac{\varepsilon}{2}, \qquad\delta= \frac{\varepsilon}{4(3+2/\varepsilon)}. \tag*{(23)}

At the first positive-radius arrival block JJ, the algorithm initializes b0=2S(J)b_0 = 2S(J) and uses the levels bn=2nb0b_n = 2^n b_0. The level never decreases. At level bb, advice AA is eligible when HA<bH_A < b, and the baseline BB is eligible when HB<δbH_B < \delta b. The algorithm prefers AA whenever it is eligible. If neither is eligible, it doubles bb until one becomes eligible. Initially AA is eligible because all requests in JJ have age zero. The smaller baseline budget limits how much the algorithm spends away from advice.

The chosen schedule is called the active source. The algorithm follows each of its services on the requests that are still physically pending, omitting empty restrictions. The other source continues only in simulation. When the active score reaches its cap, the algorithm selects again. A higher level with the same active source requires no clearance. An actual source change first clears all old physical pending requests, using (E.3) for A→BA \to B and (E.2) for B→AB \to A (lines 17 and 19 of Algorithm 3). The latter clearance includes requests that virtual advice served while BB was active.

Algorithm 3 Advice monitor: state, scores, and budget selection

Require: 0<ε≤10 < \varepsilon\le1; continuously simulated advice AA and baseline BB

1: η←ε/2\eta\leftarrow\varepsilon/2; δ←ε/[4(3+2/ε)]\delta\leftarrow\varepsilon/[4(3 + 2/\varepsilon)] 2: S(P)←PackValue⁡(P,x,g)S(P) \leftarrow\operatorname{PackValue}(P,x,g); D(P,t)←PackValue⁡(P,t−a,g)D(P,t) \leftarrow\operatorname{PackValue}(P,t-a,g) 3: For Y∈{A,B}Y \in\{A,B\} maintain its own pending set PYP_Y and paid cost pYp_Y. 4: HY(t)←pY+S(PY)+D(PY,t)H_Y(t) \leftarrow p_Y + S(P_Y) + D(P_Y,t); maintain physical pending PP separately. 5: Serve radius-zero arrivals immediately and remove their identifiers from advice. 6: At the first positive-radius arrival block JJ, admit JJ to all three queues; set b←2S(J)b \leftarrow2S(J) and active source X←AX \leftarrow A before service events. 7: function Select⁡(hA,hB,t)\operatorname{Select}(h_A,h_B,t) 8: Xold←XX_{\mathrm{old}} \leftarrow X 9: while hA≥bh_A \ge b and hB≥δbh_B \ge\delta b do 10: b←2bb \leftarrow2b 11: if hA<bh_A < b then 12: X←AX \leftarrow A 13: else 14: X←BX \leftarrow B 15: if X≠XoldX \ne X_{\mathrm{old}} then 16: if Xold=AX_{\mathrm{old}} = A then 17: Clear⁡(P,t,biased,η)\operatorname{Clear}(P,t,\mathit{biased},\eta) 18: else 19: Clear⁡(P,t,ordinary,1)\operatorname{Clear}(P,t,\mathit{ordinary},1) &nbsp;&nbsp;&nbsp;&nbsp;▷ No cleanup on a same-source level change 20: Define cap⁡(A)=b\operatorname{cap}(A)=b and cap⁡(B)=δb\operatorname{cap}(B)=\delta b.

Algorithms 3 and 4 specify budget selection and event processing. At a common timestamp, arrivals precede virtual services in a fixed order, followed by any remaining timer. A discrete event that exhausts the active cap triggers selection using tentative post-event scores, before the event is committed. This prevents a jump from being charged to an exhausted budget. On a source change, clearing the old physical queue restores the pending-set inclusion proved below: new arrivals enter after clearance, and a triggering virtual service is committed without being executed physically. Between events, the active score grows at rate ⌈∣PX∣/g⌉\lceil|P_X|/g \rceil, which determines its next cap timer. Eligibility is strict, and hence equality exhausts a cap. Throughout a block the active score is at most its cap; the inequality may be an equality just before a simultaneous event. A block is a maximal interval with the same active source, and may span several levels.

Algorithm 4 Advice monitor: arrivals, virtual services, and timers

Require: State from Algorithm 3; arrival events precede services and timers at ties

Arrival block JJ at time tt, after initialization:

  1. H^Y←pY+S(PY∪J)+D(PY∪J,t)\widehat{H}_Y \leftarrow p_Y + S(P_Y \cup J) + D(P_Y \cup J,t) for Y∈{A,B}Y \in\{A,B\}

  2. if H^X≥cap⁡(X)\widehat{H}_X \ge\operatorname{cap}(X) then

  3. Select⁡(H^A,H^B,t)\operatorname{Select}(\widehat{H}_A,\widehat{H}_B,t) ▷ Cleanup sees PP, not P∪JP \cup J

  4. Add JJ to P,PA,PBP,P_A,P_B; then process the time-tt virtual services.

Virtual service (Y,G,t)(Y,G,t), in fixed order at ties:

  1. If Y=AY=A, keep only distinct identifiers of GG in PAP_A; discard empty or infeasible proposals.

  2. H^Y←pY+c(G,t)+S(PY∖G)+D(PY∖G,t)\widehat{H}_Y \leftarrow p_Y + c(G,t) + S(P_Y \setminus G) + D(P_Y \setminus G,t)

  3. H^Z←HZ(t)\widehat{H}_Z \leftarrow H_Z(t) for the other source ZZ; Xold←XX_{\mathrm{old}} \leftarrow X

  4. if Y=XY=X and H^Y≥cap⁡(X)\widehat{H}_Y \ge\operatorname{cap}(X) then

  5. Select⁡(H^A,H^B,t)\operatorname{Select}(\widehat{H}_A,\widehat{H}_B,t) ▷ Before committing this virtual service

  6. if Y=XoldY=X_{\mathrm{old}} and X=XoldX=X_{\mathrm{old}} then

  7. Serve G∩PG \cap P physically if nonempty; remove it from PP.

  8. pY←pY+c(G,t)p_Y \leftarrow p_Y+c(G,t); PY←PY∖GP_Y \leftarrow P_Y \setminus G ▷ Always commit the virtual event

Waiting timer, after arrivals and virtual services at time tt:

  1. if HX(t)≥cap⁡(X)H_X(t) \ge\operatorname{cap}(X) then

  2. Select⁡(HA(t),HB(t),t)\operatorname{Select}(H_A(t),H_B(t),t)

After each event or selection:

  1. If PX≠∅P_X \ne\varnothing, set the next cap timer to t+[cap⁡(X)−HX(t)]/⌈∣PX∣/g⌉t + [\operatorname{cap}(X)-H_X(t)]/\lceil|P_X|/g \rceil; otherwise cancel it.

  2. Continue both virtual schedules without restarting either one.

Figure 4 summarizes the two kinds of cleanup and the order of operations at a triggering event.

Flowchart of the advice combiner

Figure 4. The advice combiner separates virtual histories from physical service. Here PP is the physical pending set, and the displayed packing costs are evaluated on the old set cleared at a switch. Returning to AA removes stale identifiers before following advice again. At a jump, selection uses tentative post-event scores, while cleanup uses pre-event pending. A triggering service is committed virtually but is not replayed physically after a source change.

Lemma E.3. During an XX block, the physical pending set is a subset of PXP_X. Each source change clears all old physical pending before the new block starts. If an arrival causes the change, the new arrivals belong to both virtual pending sets when they enter the new block.

Proof. The statement holds initially. An arrival adds the same identifiers to both virtual queues and the physical queue. An active virtual service removes all of its physically pending identifiers. Inactive services do not affect the active queue. At a source change, clearing old physical pending restores the inclusion for either new source; the event rules ensure that a triggering service is not missed by a nonempty new queue: arrivals enter after clearance, and virtual services are committed after selection (lines 4 and 12 of Algorithm 4). This proves the invariant.

Residual advice and the waiting charge

We now fix any complete feasible advice schedule, with original batches (Gj,Tj)(G_j,T_j). For consistency, we need to pay for followed advice services and for the waiting part of each A→BA \to B clearance. Both payments come from deleting physically served requests from the original advice batches. For the set ZZ of physically served request identifiers, the remaining advice cost is

Φ(Z)=∑jc(Gj∖Z,Tj),c(∅,Tj)=0.(24)\Phi(Z)=\sum_j c(G_j \setminus Z,T_j), \qquad c(\varnothing,T_j)=0. \tag*{(24)}

The sum includes original services whose times are already in the past. It is a potential used only in the proof, not a future schedule available to the algorithm. Deleting identifiers cannot increase any summand. Initially Φ(∅)=CA\Phi(\varnothing)=C_A.

Lemma E.4. Let FAF_A denote the total cost of physical services following source AA. At each A→BA \to B change ee, let PeP_e denote the old physical pending set cleared at time tet_e. Then

FA+∑eD(Pe,te)≤CA.(25)F_A+\sum_e D(P_e,t_e)\le C_A. \tag*{(25)}

Proof. We show that each followed advice service reduces Φ\Phi by its physical cost, and each A→BA \to B clearance reduces Φ\Phi by at least the corresponding DD value. Since Φ\Phi starts at CAC_A and never increases, these decreases can be summed.

At a followed advice service (Gj,Tj)(G_j,T_j), its remaining identifiers Gj∖ZG_j \setminus Z are exactly its physical restriction. Deleting them reduces the jjth summand of (E.7) by its actual service cost.

For an A→BA \to B change at time tt, we write P=PeP=P_e. By Lemma E.3, every request in PP is still pending in virtual advice. Thus each affected original batch has Tj≥tT_j\ge t. We write Qj=Gj∩PQ_j=G_j\cap P. After deleting PP, any surviving identifier in Gj∖ZG_j\setminus Z has release at least tt: all earlier arrivals were either served physically before this change or belong to PP. New arrivals that trigger the change have release exactly tt.

If an affected batch remains nonempty, its oldest surviving release therefore advances to at least tt, reducing its delay cost by at least t−min⁡r∈Qjart-\min_{r\in Q_j}a_r. Its service cost does not increase. If the batch becomes empty, its entire remaining cost is at least the same amount, since Tj≥tT_j\ge t. The nonempty QjQ_j form a capacity-feasible partition of PP, and hence the total potential drop is at least D(P,t)D(P,t). All other physical actions, including B→AB \to A cleanup, cause additional nonnegative potential drops. Summing the charged drops proves the lemma. In particular, repeated charges involving one original advice batch use successive decreases of its residual cost, never its original cost again.

During a BB block, advice may serve a request that remains physically pending. Deleting such an identifier later may affect a past advice batch. We assign no waiting credit to that deletion: the entire physical service is paid by the BB-block bound below. Before returning to AA, the full cleanup removes all such identifiers and restores the inclusion in Lemma E.3.

Figure 5 shows the waiting credit at one AA exit and how credits telescope.

Residual charging diagrams for an advice batch and successive potential drops

Figure 5. Residual charging pays for elapsed waiting only once. In (a), the original advice batch is served at Tj≥tT_j \ge t; after all old physical pending requests are deleted, its oldest surviving arrival is at least tt. The diagram shows the nonempty-residual case, and service cost can only decrease as well. In (b), the potential retains all original advice batches, including past ones. Deletions in BB blocks yield nonnegative drops but no waiting credit; the block budgets pay their physical cost.

Consistency and robustness

We next pay for the service part of each AA exit and for complete BB blocks. The following budget bounds are proved in Appendix § 13. Their key property is that a budget level cannot be reused by distinct blocks of the same source.

Let E\mathcal{E} denote the set of A→BA \to B changes, and let be+b_e^+ denote the newly selected BB level at change ee. The service-cost certificate gives

S(Pe)≤HBpost<δbe+.(26)S(P_e) \le H_B^{\mathrm{post}} < \delta b_e^+. \tag*{(26)}

This uses the post-event baseline state to cover all old requests, even when the triggering event is an arrival or a service. The cleanup itself uses the pre-event physical pending set.

For a block JJ, let bJb_J denote its last occupied level and FJF_J the cost of its followed physical services, excluding exit cleanup. If the block ends at a switch, PJP_J and tJt_J denote the old pending set and exit time. For a final block without exit cleanup, we use D(PJ,tJ)=0D(P_J,t_J)=0 below.

Lemma E.5. For an AA block,

FJ+(1+η)D(PJ,tJ)≤(1+η)bJ.(27)F_J + (1+\eta)D(P_J,t_J) \le(1+\eta)b_J. \tag*{(27)}

For a BB block, the followed services together with its exit cleanup cost at most 2δbJ2\delta b_J.

Lemma E.6. At a fixed level there is at most one AA block and one BB block. The last levels of distinct blocks of the same source are distinct, as are the newly selected levels be+b_e^+ at A→BA \to B changes. If advice is complete and feasible, then

∑e∈Ebe+≤2CA,∑J: B blockbJ≤2CA.(28)\sum_{e\in\mathcal{E}} b_e^+ \le2C_A,\qquad\sum_{J:\,B\ \mathrm{block}} b_J \le2C_A. \tag*{(28)}

For arbitrary advice, the largest level obeys

bmax⁡≤2CBδ,(29)b_{\max} \le\frac{2C_B}{\delta}, \tag*{(29)}

and the sum of all opened levels is at most 2bmax⁡2b_{\max}.

Proof of Theorem 4.1. All physical batches are feasible by construction. For consistency, we partition physical cost into followed AA services, A→BA \to B cleanups, and complete BB blocks including their exit cleanups. Lemma E.4 pays for followed advice services and the waiting part of leaving AA. The service part is bounded by (E.9), and Lemma E.5 pays for complete BB blocks. Using the two geometric sums in Lemma E.6 gives

ALG≤FA+(1+η)∑e∈ED(Pe,te)+(1+1/η)δ∑e∈Ebe++2δ∑J: B blockbJ≤[1+η+2δ(3+1/η)]CA=(1+ε)CA.\begin{aligned} \mathrm{ALG} \le F_A + (1+\eta)\sum_{e\in\mathcal{E}}D(P_e,t_e) + (1+1/\eta)\delta\sum_{e\in\mathcal{E}}b_e^+ + 2\delta\sum_{J:\,B\ \mathrm{block}}b_J \\ &\le[1+\eta+2\delta(3+1/\eta)]C_A=(1+\varepsilon)C_A. \end{aligned}

The residual-advice bound controls the first two terms by (1+η)CA(1+\eta)C_A. The BB-block term includes the cost of requests already served by virtual advice; these require no further advice charge.

For robustness, we sum (E.10) over AA blocks, bound their additional service-cost cleanup terms by (E.9), and apply the BB-block bound. These comparisons use no bound on CAC_A. The last levels of AA blocks, the last levels of BB blocks, and the newly selected levels at A→BA \to B switches each form a sequence without repetition. Bounding each sum by 2bmax⁡2b_{\max} gives

ALG≤2[(1+η)+δ(3+1/η)]bmax⁡≤4[1+ηδ+3+1η]CB=(32ε2+72ε+36)CB.\mathrm{ALG} \le2[(1+\eta)+\delta(3+1/\eta)]b_{\max} \le4\left[\frac{1+\eta}{\delta}+3+\frac{1}{\eta}\right]C_B =\left(\frac{32}{\varepsilon^2}+\frac{72}{\varepsilon}+36\right)C_B.

Since CB≤ROPT⁡(I)C_B \le R\operatorname{OPT}(I), this is (7). Completion and the polynomial-time implementation are verified in Appendix § 13. □

A lower bound on robustness

The dependence on ε\varepsilon is necessary even on inputs that fit in one batch at one location. Since these are also LAD inputs, the following lower bound applies to the general advice problem.

Theorem E.7. Fix g≥1g \ge1 and ε≥0\varepsilon\ge0. For maximum delay at one location, suppose a deterministic algorithm is (1+ε)(1+\varepsilon)-consistent against every feasible online-revealed advice stream and RR-robust. Already on inputs with at most gg requests it must satisfy

R≥1+g−11+ε(g−1).(30)R \ge1+\frac{g-1}{1+\varepsilon(g-1)}. \tag*{(30)}

Consequently, a robustness bound uniform in gg must satisfy R≥1+1/εR \ge1+1/\varepsilon for ε>0\varepsilon>0; at ε=0\varepsilon=0 no finite such bound is possible.

The proof is in Appendix § 13; the optimal dependence on ε\varepsilon is open.

Supporting proofs for the online-advice algorithm

Section 4 gives the algorithm, the residual-advice argument, and the competitive bounds. This appendix proves the packing and budget lemmas used there, verifies completion and implementation, and proves the robustness lower bound.

Packing procedures and scores

Proof of Lemma E.1. For (E.2), the procedure sorts requests by qr=max⁡{xr,wr(t)}q_r = \max\{x_r,w_r(t)\} and groups consecutive gg requests. For every zz, the number of groups whose maximum qq exceeds zz is

⌈∣{r:qr>z}∣g⌉≤⌈∣{r:xr>z}∣g⌉+⌈∣{r:wr(t)>z}∣g⌉.\left\lceil\frac{|\{r:q_r>z\}|}{g}\right\rceil\le\left\lceil\frac{|\{r:x_r>z\}|}{g}\right\rceil+\left\lceil\frac{|\{r:w_r(t)>z\}|}{g}\right\rceil.

Integrating bounds the sum of group maxima of qq by S(P)+D(P,t)S(P)+D(P,t). Each actual batch costs at most twice its maximum qq.

For (E.3), let LL denote the set {r∈P:xr≤ηwr(t)}\{r\in P:x_r\le\eta w_r(t)\}. The procedure packs LL by nonincreasing age and P∖LP\setminus L by nonincreasing radius, using groups of size at most gg in both cases. On LL, the maximum radius of a group is at most η\eta times its maximum age. On the complement, its maximum age is at most 1/η1/\eta times its maximum radius. The resulting cost is at most (1+η)D(L,t)+(1+1/η)S(P∖L)(1+\eta)D(L,t)+(1+1/\eta)S(P\setminus L), which is bounded by (E.3). ∎

Algorithm 5 implements the two clearance procedures.

Algorithm 5 Clearing pending requests at an advice switch

  1. function SortPack(P,v,gP,v,g)

  2. Sort PP by nonincreasing vrv_r, breaking ties by request identity.

  3. return consecutive groups of gg requests, with a shorter last group if needed

  4. function PackValue(P,v,gP,v,g)

  5. return ∑G∈SortPack⁡(P,v,g)max⁡r∈Gvr\sum_{G\in\operatorname{SortPack}(P,v,g)}\max_{r\in G}v_r

  6. function Clear(P,t,mode,ηP,t,\mathit{mode},\eta)

  7. wr←t−arw_r\leftarrow t-a_r for r∈Pr\in P

  8. if mode=ordinary\mathit{mode}=\mathit{ordinary} then

  9. Π←SortPack⁡(P,max⁡{x,w},g)\Pi\leftarrow\operatorname{SortPack}(P,\max\{x,w\},g)

  10. else

  11. L←{r∈P:xr≤ηwr}L\leftarrow\{r\in P:x_r\le\eta w_r\}

  12. Π←SortPack⁡(L,w,g)∪SortPack⁡(P∖L,x,g)\Pi\leftarrow\operatorname{SortPack}(L,w,g)\cup\operatorname{SortPack}(P\setminus L,x,g)

  13. Serve every nonempty G∈ΠG\in\Pi at tt; remove its members from physical pending.

Proof of Lemma E.2. Arrivals and waiting only increase packing values. Subadditivity at a service of GG gives

D(PX,t)≤max⁡r∈Gwr(t)+D(PX∖G,t),S(PX)≤max⁡r∈Gxr+S(PX∖G).D(P_X,t)\le\max_{r\in G}w_r(t)+D(P_X\setminus G,t),\qquad S(P_X)\le\max_{r\in G}x_r+S(P_X\setminus G).

The increase in pXp_X therefore pays for the total decrease of S+DS+D. To bound HXH_X, we restrict all future services of XX to PX(t)P_X(t). These restrictions form a feasible partition of the current virtual pending set. Their total future cost is at least the service cost plus the current-age cost of this partition, which is at least S(PX(t))+D(PX(t),t)S(P_X(t))+D(P_X(t),t).

For (E.5), we partition PP using restrictions of the past services of BB, together with a partition of PB(t)P_B(t) minimizing service cost. Past service costs are at most pB(t)p_B(t), and restriction cannot increase them. This proves the bound even when PP contains requests that BB has already served.

Block budgets and geometric sums

Proof of Lemma E.5. Restrictions of source services cannot increase cost, and hence FJF_J is at most the source’s paid-cost increment during the block. Just before a source-changing event, the old active score is still within its cap; the event causing a jump has not been committed. Monotonicity under subsets gives D(PJ,tJ)≤D(PX,tJ)D(P_J,t_J) \le D(P_X,t_J) and S(PJ)≤S(PX)S(P_J) \le S(P_X). For AA, these facts bound FJ+D(PJ,tJ)F_J + D(P_J,t_J) by bJb_J, proving (E.10). For BB, apply (E.2) and bound paid cost plus twice S+DS + D by twice the old cap δbJ\delta b_J. The same bounds hold without exit cleanup for the final block.

Proof of Lemma E.6. Once AA is ineligible at a level, monotonicity of HAH_A prevents it from becoming eligible there again. Thus B→AB \to A requires a higher level. The same observation proves the distinctness claims, including when a block spans several levels without a cleanup.

Whenever a level is selected for BB, preference for AA implies b≤HA≤CAb \le H_A \le C_A. This remains true for the last level of a BB block: each same-source level increase again tests AA first. Each sum in (E.11) is therefore a sum of distinct dyadic levels at most CAC_A, and is at most 2CA2C_A. They are two separate sums and will have separate coefficients in the cost bound.

Initially b0=2S(J)≤2CBb_0 = 2S(J) \le2C_B. Every subsequent level is twice a level where both eligibility tests failed, and hence HB≥δbH_B \ge\delta b at that failed level. Since HB≤CBH_B \le C_B and δ≤1\delta\le1, this proves (E.12). The final assertion is a geometric sum.

Completion and implementation

We finish the proof of Theorem 4.1 by verifying completion and online computation. On a finite input, CBC_B is finite, and hence (E.12) permits only finitely many levels and source changes. A final BB block completes because BB does. A final AA block with a request pending forever would have unbounded D(PA,t)D(P_A,t), exhausting its finite cap. Hence all requests are eventually served without an end-of-input signal. The cost bounds can first be applied to every finite prefix of physical actions, and hence this completion argument does not assume either bound circularly.

Both packing values and both cleanups require only sorting. For fixed PXP_X, ages have a fixed order and D(PX,t)D(P_X,t) is affine with slope ⌈∣PX∣/g⌉\lceil|P_X|/g \rceil. Timers therefore use only current requests. Discrete jumps use the newly revealed event and the current source states; intermediate ineligible dyadic levels can be skipped directly. Under rational input encoding, including ε\varepsilon, the number of levels and the arithmetic overhead are polynomial whenever BB is polynomially simulable. Malformed events are charged to the advice input length; as usual, event streams are locally finite.

Proof of the robustness lower bound

Proof of Theorem E.7. We normalize the setup cost to one. The adversary releases the first request at time zero and advises its immediate singleton service. After the algorithm serves request ii, the adversary waits δi>0\delta_i > 0 before releasing request i+1i+1, again with immediate singleton advice. The construction stops after request gg. Consistency forces the algorithm to serve each request even if no others arrive.

Let xix_i denote the wait of request ii, and write X=∑i<gxiX = \sum_{i<g} x_i. On the input stopped after g−1g-1 requests, advice costs g−1g-1, while the algorithm costs at least (g−1)+X(g-1) + X. Since future advice is not revealed, its execution through these services is identical to that on the full input. Hence X≤ε(g−1)X \le\varepsilon(g-1). On the full input, online cost is at least g+Xg+X. All requests fit together, and hence serving them at the final arrival costs at most 1+X+Δ1+X+\Delta, where Δ=∑i<gδi\Delta=\sum_{i<g}\delta_i. For Δ<g−1\Delta<g-1, the function (g+X)/(1+X+Δ)(g+X)/(1+X+\Delta) decreases in XX. Letting Δ↓0\Delta\downarrow0 proves (E.13); g=1g=1 is immediate. Letting g→∞g\to\infty gives the stated lower bounds on robustness uniform in capacity.

Proof of the arbitrary-size LAD extension

We prove the guarantee stated in § 3.5.

Proof of Corollary 3.4. Under the preprocessing of § 3.5, every closed small-item bin has load greater than K/2K/2, since the rejected item has size at most K/2K/2. Large-item singleton batches also have load greater than K/2K/2. Each preprocessed batch at radius yy costs at most 2y2y. If PP is the set of preprocessed requests, then

ALGpre≤4K∑r∈Psryr\mathrm{ALG}_{\mathrm{pre}} \le\frac{4}{K}\sum_{r\in P}s_r y_r

The residual cohort has total size at most KK, even if its cardinality is arbitrarily large.

For the weighted path load defined in § 3.5, the same integration argument gives

∑r assigned to usr≤K;\sum_{r\text{ assigned to }u}s_r \le K;

whole cohorts, and hence indivisible requests, remain intact. Service times and the bound 3Ru3R_u are unchanged.

The weighted certificates are

βr=srRuK,γr=sryvMv\beta_r=\frac{s_rR_u}{K},\qquad\gamma_r=\frac{s_ry_v}{M_v}

for an own-cohort request of a heavy root vv.

All other requests receive zero γ\gamma weight. If a heavy root has Mv=0M_v=0, we assign its whole weight yvy_v to one designated request in the cohort that created it. Such a root is top-level: with a selected ancestor, a zero-mass cohort adds nothing to a feasible path load and is accepted. Thus it cannot occur among the nonmaximal heavy roots in the certificate proof.

For any feasible offline batch BB, we write αB=K−1∑r∈B∖Psr≤1\alpha_B=K^{-1}\sum_{r\in B\setminus P}s_r\le1. Its preprocessed mass is at most K(1−αB)K(1-\alpha_B). The proofs of Lemmas D.2 and D.3 now give

∑r∈Bβr≤DB+(2+αB)YB,∑r∈Bγr≤DB+(2+αB/θ)YB.\sum_{r\in B}\beta_r\le D_B+(2+\alpha_B)Y_B,\qquad \sum_{r\in B}\gamma_r\le D_B+(2+\alpha_B/\theta)Y_B.

Indeed, the integral over each maximal represented home is unchanged; the remaining terms are bounded by the total size αBK\alpha_BK in place of a request count. Immediate child-root intervals are still disjoint, and hence Lemma D.4 charges each request at most βr/(1−θ)\beta_r/(1-\theta). Combining these bounds with preprocessing gives exactly (D.3). The deterministic and random-scale conclusions follow with the same constants. The operations use cohort packing, tree ancestry, and arithmetic on revealed data; no optimum bin packing is required.

Algorithm 6 replaces only the cohort preprocessing and the load units in Algorithm 1. It retains the final nonempty bin even when its load is exactly KK.

Algorithm 6 Weighted cohort preprocessing for the path-load algorithm
Require: Home cohort $Q$ of width $y$, revealed at $b$; capacity $K$
1: Serve every $r \in Q$ with $s_r > K/2$ as a singleton at $b$.
2: $T \leftarrow \varnothing$
3: for remaining requests $r$ in a fixed order do
4:   if $\sum_{q \in T} s_q + s_r > K$ then
5:     Serve $T$ at $b$; $T \leftarrow \varnothing$.
6:   $T \leftarrow T \cup \{r\}$
7: if $T \ne \varnothing$ then
8:   Pass $T$ as one residual cohort to Algorithm 1.
9: Use $M_v = \sum_{r \in T} s_r$ and replace $g$ by $K$ in every path-load term.
10: Leave assignments, ancestor selection, and root service times unchanged.
11: Retain a nonempty zero-load residual cohort; nonemptiness is not a load test.

Top-kk delay at one location

The fixed-location case also admits a constant guarantee when a batch pays the sum of its largest waiting times. Retain the cardinality capacity g∈Z≥1g \in\mathbb{Z}_{\ge1} and let k∈Z≥1k \in\mathbb{Z}_{\ge1} denote the number of charged waits. A batch of at most gg requests costs its fixed setup w>0w > 0 plus Top⁡k\operatorname{Top}_k, the sum of its largest min⁡{k,∣Q∣}\min\{k, |Q|\} waiting times. The algorithm and comparator use the same g,k,wg,k,w. Requests arriving together retain their multiplicities.

The rule. Keep requests in arrival order. At each arrival epoch, serve full batches of gg oldest pending requests until fewer than gg remain. Serve the remaining buffer when its top-kk waiting sum first reaches ww. Full-batch actions precede a simultaneous timer. New arrivals have zero age, so they do not jump the clock; full-batch actions clear the entire old buffer before any newly created residual buffer can age.

Theorem H.1 (A uniform fixed-location bound). The full-or-top-kk rule is strictly 3-competitive for every g,k≥1g,k \ge1, independently of both parameters. For g≥2g \ge2, no deterministic algorithm has competitive ratio strictly below two.

Proof. Fix a feasible comparator OO and let COC_O be its total setup cost. For each of its eventual batches QQ, let nQ(t)n_Q(t) count the requests assigned to QQ that have arrived and are still unserved. Then

DO(k)=∫0∞∑Q∈Omin⁡{k,nQ(t)} dt.(31)D_O^{(k)}=\int_0^\infty\sum_{Q\in O}\min\{k,n_Q(t)\}\,\mathrm{d}t. \tag*{(31)}

This follows by integrating the waits of the oldest kk requests in each batch.

The algorithm’s positive-length buffer episodes have disjoint interiors. Each ends by clearing the old buffer in a full batch or a timer batch. All their delays are at most ww, and timer batches have delay exactly ww. For comparison bookkeeping, reveal arrivals, perform all online full-batch actions, then the comparator’s actions, and finally any online timer. Mark an episode when the comparator first serves a request currently in its buffer. At a comparator action there is only one current buffer, and no further buffer can start after the timer at that timestamp. Thus marked episodes have distinct comparator batch witnesses, and their total delay is at most COC_O. Throughout an episode ending unmarked, all buffer requests are still pending offline. Partition them by their eventual comparator batches. The inequality

min⁡{k,∑QxQ}≤∑Qmin⁡{k,xQ}\min\{k,\sum_Q x_Q\}\le\sum_Q\min\{k,x_Q\}

bounds the buffer’s rate by the integrand in (H.1). Disjoint episode interiors therefore give DA(k)≤CO+DO(k)D_A^{(k)}\le C_O+D_O^{(k)}. This also handles an episode cleared by an arrival action whose requests are served offline at the same endpoint: its open interval is still chargeable.

Let FF and TT count full and timer batches. Since full batches contain gg distinct requests, Fw≤Nw/g≤COFw\le Nw/g\le C_O. Also Tw≤DA(k)Tw\le D_A^{(k)}. Consequently,

ALG=Fw+Tw+DA(k)≤CO+2DA(k)≤3CO+2DO(k)≤3cost⁡(O).\mathrm{ALG}=Fw+Tw+D_A^{(k)}\le C_O+2D_A^{(k)}\le3C_O+2D_O^{(k)}\le3\operatorname{cost}(O).

A nonempty residual buffer has clock rate at least one and reaches its timer in finite time. There are at most NN services, so completion requires no end notification. If g=1g=1, immediate service is optimal.

For g≥2g\ge2, the two offset adjacent-pair schedules in the proof of Theorem A.3 remain feasible. Each offline pair is served at its later arrival and has waits (Δ,0)(\Delta,0); each algorithm batch in that adversarial construction is a singleton. Their costs are unchanged for every kk, so the deterministic lower bound of two follows.

The old proof of a factor two cannot simply replace “short span” by “small top-kk cost.” For g=3g=3, k=2k=2, and w=4w=4, arrivals (0,0,3,3,3,3)(0,0,3,3,3,3) have three maximal consecutive prefixes with endpoint top-2 cost at most four: (0,0)(0,0), (3,3,3)(3,3,3), and (3)(3). Yet the two groups (0,3,3)(0,3,3) and (0,3,3)(0,3,3) both satisfy this condition. Thus the corresponding greedy minimum-number lemma is false. The theorem above concerns the fixed-location case; it does not change the general LAD or advice guarantees elsewhere in the paper.

Advice Experiment Protocol and Additional Results

Instances, capacities, and the exact benchmark

We use 20 fixed seeds per family, indexed 0,…,190,\ldots,19, and 12 requests per instance. All arrivals and radii are quarter-integers. Before evaluation we subtract the earliest arrival from every timestamp and sort requests by arrival, retaining distinct identifiers at ties. The generator seed is 2026111300+s+10000f2026111300+s+10000f, where ss is the instance index and f∈{0,1,2}f\in\{0,1,2\} is the family index. The same requests are evaluated at all three capacities.

FamilyUnshifted arrival distributionRadius distribution
BurstyUniform center in {0,1,3,6}\{0,1,3,6\}, plus 0 or 1/4Uniform in {1,2,4,8}\{1,2,4,8\}
Spread-outUniform quarter-grid in [0,32][0,32]Uniform in {1/4,1,4,16}\{1/4,1,4,16\}
Mixed-scaleUniform quarter-grid in [0,8][0,8]Uniform in {2j:−2≤j≤5}\{2^j:-2\le j\le5\}

Table 1.

Arrivals and radii are independently generated within these specified families. These distributions are controlled synthetic tests, not calibrated demand models.

For a nonempty request subset GG with ∣G∣≤g|G|\le g, its canonical batch cost is

c(G)=max⁡r∈Gxr+max⁡r∈Gar−min⁡r∈Gar.c(G)=\max_{r\in G}x_r+\max_{r\in G}a_r-\min_{r\in G}a_r.

It is attained by serving at the last arrival of GG; later service only increases cost. Thus exact offline optimization on these finite instances is set partitioning. With V(∅)=0V(\varnothing)=0, we compute

V(S)=min⁡∅≠G⊆S, ∣G∣≤gmin⁡S∈G[c(G)+V(S∖G)].V(S)=\min_{\substack{\varnothing\ne G\subseteq S,\ |G|\le g\\ \min S\in G}}\left[c(G)+V(S\setminus G)\right].

The restriction to the least identifier removes permutation duplicates. Costs are computed as integers in quarter units, and the minimizing batches are reconstructed. This exponential oracle is used only for the 12-request benchmark; no polynomial-time exact algorithm for general capacitated LAD is claimed. Independent restricted-growth partition enumeration agrees on 72 six-request/capacity tests. The single-location gap formula is checked on two additional instances.

Algorithms and information available

The robust source is exactly path-load with fixed scale λ=1\lambda=1 and the deterministic tie order in Algorithm 1. The monitor uses η=ε/2\eta=\varepsilon/2 and δ=ε/[4(3+2/ε)]\delta=\varepsilon/[4(3+2/\varepsilon)] without tuning. We also record the independent-class full-or-age baseline from § 3.1.

The experiment driver constructs complete advice and baseline event lists. Decisions use only current virtual queues, paid costs, the event currently revealed, and the endogenous score timer. Future advice is accessed only by the driver and invariant checker. Arrivals precede virtual services at ties; advice services precede baseline services; waiting timers are processed after the timestamp’s arrivals and services. Physical requests are served once, in batches of size at most gg. Cost includes all services after the final arrival, without sending an end-of-input notification to the algorithm.

The exact-rational simulator is derived from the existing event audit. For every run, it checks complete service, capacity, source-score monotonicity, the residual-advice potential charge, and the stated consistency/robustness inequalities. A separate cost evaluator recomputes costs from the recorded physical schedule. An additional 111 prefix checks test that the path-load schedule before a cutoff does not change when future input is deleted. The six-request example in Figure 1 has checked algorithm cost 30. These finite checks support implementation fidelity; the universal guarantees are proved in the preceding appendices.

Two advice corruption mechanisms

Systematic lateness. Take an exact optimal schedule with mm batches and delay every service by ρ OPT/m\rho\,\mathrm{OPT}/m. Its request partition is retained, so it remains complete and capacity feasible, and its cost is exactly (1+ρ) OPT(1+\rho)\,\mathrm{OPT}. We use

ρ∈{0,0.1,0.3,1,3,10,30,100,300,1000,10000}.\rho\in\{0,0.1,0.3,1,3,10,30,100,300,1000,10000\}.

The large values intentionally expose the fallback regime of the conservative monitor. They are not a claim about typical prediction errors. In total this part has 180×11×3=5940180\times11\times3=5940 runs.

Feasible repartitioning. For α∈{0,0.2,0.4,0.6,0.8,1}\alpha\in\{0,0.2,0.4,0.6,0.8,1\}, select ⌊αm⌋\lfloor\alpha m\rfloor optimal batches using a seeded random order. Shuffle their request identifiers and form groups of at most gg, serving each at its last arrival. Other batches are retained. This changes the partition while maintaining feasibility and completion. The partition shuffle seed is 910000+s+100f910000+s+100f, held fixed as α\alpha changes. Advice quality need not be monotone in α\alpha. There are 180×6×3=3240180\times6\times3=3240 runs. The realized advice-to-OPT ratio lies between 1 and 4.053; every monitor has the same physical cost as following advice and makes no nonempty switch in this regime. Figure 7 therefore shows their common cost, separately by capacity.

Figure 7. Capacity-feasible partition corruption. All three monitor settings coincide with follow-advice on these tests. Bands are pointwise 95% stratified bootstrap intervals over request-instance seeds.

Figure 6. All three input families separately, using the same instances and parameters as the pooled main-text plot. Dotted gray is follow-advice; dashed black is the path-load baseline. Each curve averages over 20 seeds and three capacities. No family or seed is omitted.

Aggregation, uncertainty, and reproducibility

The plotted estimator is the mean finite-input ratio ALG⁡(I)/OPT⁡(I)\operatorname{ALG}(I)/\operatorname{OPT}(I), not a long-run stochastic ratio. In the pooled curves, we resample the 20 seeds within each family, retaining all three capacity variants of a sampled instance together. We use 2000 stratified paired cluster-bootstrap replicates with seed 20261113 and report pointwise percentile intervals. They are not simultaneous confidence bands or evidence for untested input families. Capacity-specific intervals use the corresponding fixed-capacity data.

Every generated input and all 9180 outcomes are included in the accompanying anc/experiments/results/advice_experiments.json. The self-contained monitor_core.py, run_advice_experiments.py, and plot_advice.py reproduce the data and plots. Exact simulation uses the Python standard library; plotting additionally uses NumPy and Matplotlib. The unfavorable middle-corruption and poor-advice results are retained. They identify conservative switching constants as a limitation of the present implementation, alongside the benefit of optimal advice.

Additional information-flow audit. The script anc/experiments/reviewer_audit.py changes both future arrivals and future advice while preserving each observed prefix. Across 540 paired runs, all physical actions and budget decisions through the cutoff agree; these prefixes include 77 nonempty switches. It also rechecks all 9180 exact cost records, the 180 optimal advice schedules, and the independent small-instance oracle tests. This finite differential check supports implementation fidelity and does not replace the online-information argument in the proof. Lateness and repartitioning have different realized error ranges, so their comparison does not isolate error structure at a matched advice-to-OPT ratio. The original outcomes and algorithm constants are unchanged.

References

  1. [1]Yasemin Aksoy and S. Selcuk Erenguc. Multi-item inventory models with co-ordinated replenishments: A survey. Int. J. Oper. Prod. Manag., 8(1):63–73, 1988.
  2. [2]Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In Proc. FOCS, pages 60–71, 2019.arxiv.org/abs/1904.07131
  3. [3]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, and Pavel Veselý. Online algorithms for multilevel aggregation. Oper. Res., 68(1):214–232, 2020.DOI
  4. [4]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, and Pavel Veselý. New results on multi-level aggregation. Theor. Comput. Sci., 861:133–143, 2021.DOI
  5. [5]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Dorian Nognenġ, and Jiří Sgall. Better approximation bounds for the joint replenishment problem. In Proc. SODA, pages 42–54, 2014.
  6. [6]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiří Sgall, and Grzegorz Stachowiak. Online control message aggregation in chain networks. In Proc. WADS, pages 133–145, 2013.DOI
  7. [7]Jannis Blauth, Vera Traub, and Jens Vygen. Improving the approximation ratio for capacitated vehicle routing. arXiv:2011.05235, 2020.arxiv.org/abs/2011.05235
  8. [8]Carlos Brito, Elias Koutsoupias, and Shailesh Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proc. SODA, pages 627–635, 2004.
  9. [9]Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Proc. SODA, pages 1235–1244, 2017.
  10. [10]Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. Online make-to-order joint replenishment model: Primal dual competitive algorithms. In Proc. SODA, pages 952–961, 2008.
  11. [11]José R. Correa and Nicole Megow. Clique partitioning with value-monotone submodular cost. Discrete Optim., 15:26–36, 2015.DOI
  12. [12]Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. On-line analysis of the TCP acknowledgment delay problem. J. ACM, 48(2):243–273, 2001.DOI
  13. [13]Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Hadas Shachnai, Mordechai Shalom, Tami Tamir, and Shmuel Zaks. Minimizing total busy time in parallel scheduling with application to optical networks. Theor. Comput. Sci., 411(40–42):3553–3562, 2010.
  14. [14]Takuro Fukunaga, Afshin Nikzad, and R. Ravi. Deliver or hold: Approximation algorithms for the periodic inventory routing problem. In Proc. APPROX/RANDOM, pages 209–225, 2014.DOI
  15. [15]Suresh K. Goyal and Ahmet T. Satir. Joint replenishment inventory control: deterministic and stochastic models. Eur. J. Oper. Res., 38(1):2–13, 1989.DOI
  16. [16]Dev Joneja. The joint replenishment problem: new heuristics and worst case performance bounds. Oper. Res., 38(4):711–723, 1990.DOI
  17. [17]Shahin Kamali and Alejandro López-Ortiz. Efficient online strategies for renting servers in the cloud. In Proc. SOFSEM, pages 277–288, 2015.arxiv.org/abs/1408.4156
  18. [18]Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e − 1). In Proc. STOC, pages 502–509, 2001.DOI
  19. [19]Sanjeev Khanna, Joseph Seffi Naor, and Dan Raz. Control message aggregation in group communication protocols. In Proc. ICALP, pages 135–146. Springer, 2002.DOI
  20. [20]Yusen Li, Xueyan Tang, and Wentong Cai. On dynamic bin packing for resource allocation in the cloud. In Proc. SPAA, pages 2–11, 2014.DOI
  21. [21]Yusen Li, Xueyan Tang, and Wentong Cai. Dynamic bin packing for on-demand cloud resource allocation. IEEE Trans. Parallel Distrib. Syst., 27(1):157–170, 2016.DOI
  22. [22]Young-San Lin and Alex Turoczy. Improved and parameterized algorithms for online multi-level aggregation. In Proc. SWAT, pages 31:1–31:17, 2026.arxiv.org/abs/2511.23211
  23. [23]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online bin packing with per-bin maximum delay. arXiv:2609.29589, 2026.arxiv.org/abs/2609.29589
  24. [24]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online covering with maximum delay under subadditive service costs. arXiv:2609.32675, 2026.arxiv.org/abs/2609.32675
  25. [25]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Learning-augmented and randomized algorithms for line aggregation with delays. arXiv:2607.27807, 2026.arxiv.org/abs/2607.27807
  26. [26]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Online multi-level aggregation with per-batch maximum delay. arXiv:2608.06796, 2026.arxiv.org/abs/2608.06796
  27. [27]Mathieu Mari, Michał Pawłowski, Runtian Ren, and Piotr Sankowski. Online multi-level aggregation with delays and stochastic arrivals. In Proc. ISAAC, pages 49:1–49:20, 2024.arxiv.org/abs/2404.09711
  28. [28]Jeremy McMahan. A D-competitive algorithm for the multilevel aggregation problem with deadlines. arXiv:2108.04422, 2021.arxiv.org/abs/2108.04422
  29. [29]George B. Mertzios, Mordechai Shalom, Ariella Voloshin, Prudence W. H. Wong, and Shmuel Zaks. Optimizing busy time on parallel machines. Theor. Comput. Sci., 562:524–541, 2015.
  30. [30]Tim Nonner. Capacitated max-batching with interval graph compatibilities. Theor. Comput. Sci., 613:79–93, 2016.
  31. [31]Runtian Ren and Xueyan Tang. Busy-time scheduling on heterogeneous machines. In Proc. IPDPS, pages 306–315, 2020.DOI
  32. [32]Runtian Ren, Xueyan Tang, Yusen Li, and Wentong Cai. Competitiveness of dynamic bin packing for online cloud server allocation. IEEE/ACM Trans. Netw., 25(3):1324–1331, 2017.DOI
  33. [33]Steven S. Seiden. A guessing game and randomized online algorithms. In Proc. STOC, pages 592–601, 2000.DOI
  34. [34]Mordechai Shalom, Ariella Voloshin, Prudence W. H. Wong, Fencol C. C. Yung, and Shmuel Zaks. Online optimization of busy time on parallel machines. Theor. Comput. Sci., 560:190–206, 2014.
  35. [35]Xueyan Tang, Yusen Li, Runtian Ren, and Wentong Cai. On first fit bin packing for online cloud server allocation. In Proc. IPDPS, pages 323–332, 2016.DOI
  36. [36]Jingyang Zhao and Mingyu Xiao. Improved approximation algorithms for capacitated vehicle routing with fixed capacity. In Proc. MFCS, pages 931–939, 2025.

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

Generative AI tools

View statement
Looking for related papers…
Contents