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 kk 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.

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. [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 kk 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 kk. 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.9.

  • 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.

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 § 6 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 capacitated max-batching model [30]. 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 kk intervals with a common intersection and costs their maximum weight. The problem is strongly NP-hard already for k=3k = 3 and admits a PTAS for every fixed kk. 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 § 8. 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 its consistency and robustness analysis. The appendices contain the fixed-location results, the baseline upper bound, capacity transfer, and supporting proofs for advice and arbitrary request sizes.

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 k≥1k \ge1. A service (Q,t)(Q,t) completes a nonempty set QQ of at most kk 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 k≥2k \ge2 and positive radii: for k=1k=1, immediate singleton service is optimal, and zero-radius requests can always be served immediately for free. § 3.9 extends the model to arbitrary indivisible request sizes.

An O(1)O(1)-competitive algorithm for LAD

In the uncapacitated algorithm of Lu et al. [26], a dynamic program sets a deadline for the current pending block, which is then served in one batch. Its analysis uses the fact that batches with overlapping arrival spans can be merged without increasing cost. Capacity changes both steps: a pending block may contain more than kk requests, and merging may be infeasible. Splitting a block at its deadline can repeat its maximum delay across several batches; serving only part of it leaves old requests for later services. Neither modification inherits the original cost bound.

Before developing the new algorithm, we examine the loss incurred by serving distance classes independently. The instance below shows that capacity alone does not explain this loss: all its requests fit in one batch, but the algorithm fails to share their waiting costs.

Why independent distance classes lose a logarithmic factor

The dyadic-class algorithm first rounds each positive radius upward to a power of two. At each rounded radius xx, it independently runs the full-or-age algorithm with setup xx: whenever at least kk requests are pending, it serves the kk oldest; otherwise, it serves all pending requests when the oldest reaches age xx. Full batches take priority over the age rule; classes never share a service. Algorithm 1 states this baseline.

Algorithm 1 The independent-class LAD baseline

Require: Capacity kk

  1. Serve zero-radius requests immediately for free.

  2. Assign every other request rr to its rounded radius yr=2⌈log⁡2xr⌉y_r = 2^{\lceil\log_2 x_r \rceil}.

  3. At each rounded radius yy, run FullOrAge(k,y)(k,y) from Algorithm 5.

  4. Execute the resulting services independently; do not merge groups.

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

The proof of the upper bound appears in Appendix § 7.

A matching lower-bound instance. Let m=⌊log⁡2(k+1)⌋m = \lfloor\log_2(k + 1) \rfloor and R=2m−1R = 2^{m-1}. For each i=0,…,m−1i = 0, \ldots, m - 1, set xi=2ix_i = 2^i and release one request at radius xix_i at each time 2jxi2j x_i, where j=0,…,R/xi−1j = 0, \ldots, R/x_i - 1. The total number of requests is

∑i=0m−1Rxi=2m−1≤k.\sum_{i=0}^{m-1} \frac{R}{x_i} = 2^m - 1 \le k.

At radius xix_i, every request reaches age xix_i before the next request in its class arrives. The algorithm therefore serves it alone at time (2j+1)xi(2j + 1)x_i, paying 2xi2x_i. Each class contributes 2R2R, so ALG=2mR\mathrm{ALG} = 2mR.

Offline can serve all requests in one batch at the last arrival time 2R−22R - 2. This batch respects capacity, has maximum radius RR and maximum waiting time 2R−22R - 2, and costs 3R−23R - 2. Consequently,

ALGOPT≥2mR3R−2≥2m3=Ω(log⁡k).\frac{\mathrm{ALG}}{\mathrm{OPT}} \ge\frac{2mR}{3R - 2} \ge\frac{2m}{3} = \Omega(\log k).

Thus the logarithmic bound is tight for this algorithm. The loss occurs even though all requests in the entire input fit in one batch: independent class timers repeatedly pay waiting costs that a shared batch pays only once.

The main idea: Next Fit along nested intervals

We therefore control which groups can join a future batch while they wait. The challenge is to retain sharing across distances without making small groups wait too long for a distant request. Counting requests alone ensures that a batch fits, but does not pay for groups that must be served separately. Our path load accounts for both group size and waiting time scale. A failed admission test opens a new batch and provides a charge for its cost. Later groups inside that batch’s interval try to join it, rather than returning to its ancestors: this is the Next Fit idea along nested intervals. We explain the rule and its analysis through an example before giving the formal proofs.

Giving a group a time scale. For this explanation, suppose radii are powers of two. For each radius yy, collect the requests arriving in [b−y,b)[b-y,b), where bb is a multiple of yy. At time bb, this group is completely known. Serve full batches of kk requests immediately and retain the remainder as a single group, called a cohort. A full batch costs at most 2y2y: its service cost is yy and its maximum delay is at most yy. These batches are paid for by the volume lower bound

OPT⁡≥1k∑rradius⁡(r).\operatorname{OPT} \ge\frac{1}{k}\sum_{r}\operatorname{radius}(r).

Indeed, a batch’s largest radius is at least the sum of its requests’ radii divided by kk.

Give the remaining cohort the home interval [b,b+y)[b,b+y). It could be served at the right endpoint for cost at most 3y3y. The home intervals are nested or disjoint, which provides a way to combine different radii: a cohort may instead join the future batch of a containing interval. We call an interval selected to open a batch a root, and call that root the owner of the cohorts assigned to it. Its batch is served at its right endpoint. Larger intervals are processed first when their left endpoints coincide. Thus a containing root is already known when a cohort decides whether to join it. Assignments and service times are never revised.

Why count load rather than requests? Suppose a root has interval length RR. A cohort of MM requests with home length yy reserves MR/kMR/k units of area under this interval. Spread this area uniformly over its own home. Its load there is

MRky=Mk⋅Ry.\frac{MR}{ky}=\frac{M}{k}\cdot\frac{R}{y}.

The first factor is the fraction of capacity used; the second compares the owner’s time scale with the cohort’s own time scale. A short home therefore contributes more load than a long home with the same number of requests. We allow the assignment only if the total load stays at most one throughout the new home. The total area is then at most RR. Since every assigned request contributes area R/kR/k, at most kk requests can be assigned to this root.

When the test fails, the cohort opens its own root. Later cohorts inside this new interval test admission to the new root, rather than returning to its ancestors. This is the Next Fit idea along each path of nested intervals. Disjoint subintervals can still use the earlier root. This distinction will be essential when we account for the cost of rejected cohorts. Section 3.6 shows that trying older roots first can destroy the certificate used to compare these costs with offline batches.

A worked example. Let k=8k=8. Two requests of radius 88 arrive at time 00; two 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 all six requests. No full batch is removed in preprocessing.

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 8, the radius-8 cohort opens a root with home [8,16)[8,16), and its two requests contribute load 2/8=1/42/8=1/4. The radius-4 cohort has home [8,12)[8,12) and adds load 2⋅8/(8⋅4)=1/22\cdot8/(8\cdot4)=1/2 there. It is accepted. At time 10, the radius-2 request reveals its home [10,12)[10,12). Its prospective load is 8/(8⋅2)=1/28/(8\cdot2)=1/2, taking the total on this home to 5/45/4. It is rejected even though a fifth request would fit in the batch. Instead, it opens a root and is served at time 12, for cost 2+(12−8)=62+(12-8)=6.

At time 12, the last radius-4 request reveals home [12,16)[12,16). This home is disjoint from [8,12)[8,12), and its load test is only 1/4+1/4=1/21/4+1/4=1/2. It joins the first root. The resulting five-request batch is served at time 16, for cost 8+(16−0)=248+(16-0)=24. The algorithm’s total cost is therefore 30.

Offline can serve all six requests at time 8, for cost 8+8=168+8=16. Compared with this feasible solution, the algorithm pays more to fix its groups and service times online. Leaving a capacity slot unused preserves a load budget for subsequent groups.

What pays for opening another batch? The example has load 3/43/4 already present throughout the rejected home [10,12)[10,12). The area under this old load is 3/23/2, enough to pay its length 2 within a constant factor. More generally, a failed test means that either the incoming cohort contributes at least 1/21/2, or the old load exceeds 1/21/2 on its home. In the first case, charge the new root’s length to the requests that created it. In the second, charge it to twice the old load integrated over its home. A root’s actual batch cost is at most three times its length, so it suffices to pay for these lengths.

The second charge must not reuse the same area at every smaller scale. This is exactly why we use Next Fit: the first rejected home becomes responsible for later rejections inside it. The homes that charge a fixed parent root are disjoint. A request assigned to that parent therefore pays at most twice its reserved area in total, even if many smaller roots are subsequently opened. Descendants of a child use the child’s assigned requests, not the parent’s requests.

Why are these charges lower bounds on the offline cost? We first charge online roots to requests and then bound these charges inside each feasible offline batch. The second comparison is necessary because a batch may combine requests from different roots without taking whole cohorts.

Fix an offline batch whose largest radius is YY and whose arrival span is DD. Its cost is at least Y+DY + D. Requests with owners of length at most YY have small reserved-area charges, whose sum is controlled by the batch’s capacity. For larger owners, Next Fit gives a unique-owner property: inside each maximal home represented in the batch, all requests owned above that home share the same owner. Its load is at most one, so their area is bounded by the home length. These maximal homes are disjoint and lie in a time interval of length D+2YD + 2Y.

The own-cohort charges admit a similar division: maximal roots are controlled by disjoint intervals, and the remaining per-request charges by capacity. Both certificates are therefore bounded by a constant times the offline batch cost. Summing over its partition gives the desired comparison with OPT. The formal analysis below establishes these bounds, optimizes the threshold, and accounts for preprocessing and radius rounding.

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

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

These deterministic guarantees hold also for adaptively generated inputs.

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 kk 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(⌊aryr⌋+1).b_r = y_r\left(\left\lfloor\frac{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 kk 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 2).

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/k4y/k times its cardinality. If PP denotes the set of preprocessed requests, then

ALG⁡pre≤4k∑r∈Pyr.(2)\operatorname{ALG}_{\mathrm{pre}} \le\frac{4}{k}\sum_{r\in P} y_r. \tag*{(2)}

We use the loose factor four so that the same accounting also applies to arbitrary sizes in Appendix § 10. 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/(kyv)M_vR_u/(ky_v) over IvI_v. Its integral is MvRu/kM_vR_u/k, 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⊆IwMwRukyw+MvRukyv.(3)L_u(v)=\sum_{\substack{w\ \text{already assigned to }u\\ I_v\subseteq I_w}}\frac{M_wR_u}{ky_w}+\frac{M_vR_u}{ky_v}. \tag*{(3)}

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 2). 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 (3) 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 3.3. 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 uMwRukyw1Iw(t).f_u(t)=\sum_{w\ \text{assigned to }u}\frac{M_wR_u}{ky_w}\mathbf{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/k≤1M_u/k\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

Ruk∣{r:r is assigned to u}∣=∫Iufu(t) dt≤Ru,\frac{R_u}{k}\left|\{r:r\text{ is assigned to }u\}\right|=\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. □

Algorithm 2 summarizes the complete event-driven rule.

Algorithm 2 Path-load aggregation for LAD

Require: Capacity kk; one fixed scale λ>0\lambda> 0; deterministic tie orders Use λ=1\lambda= 1 for the deterministic version; for Corollary 3.7, 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: 2: 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) 3: Store rr in the cohort with home [br,br+yr)[b_r, b_r + y_r). At a virtual arrival time bb: 4: for nonempty homes [b,b+y)[b,b+y) in decreasing yy do 5: Q←Q \leftarrow the requests stored for this home 6: while ∣Q∣≥k|Q| \ge k do 7: Serve the first kk requests of QQ at bb and remove them from QQ. 8: if Q≠∅Q \ne\varnothing then 9: Create cohort vv with Iv=[b,b+y)I_v = [b,b+y), yv=yy_v = y, and Mv=∣Q∣M_v = |Q|. 10: u←u \leftarrow the selected strict ancestor of IvI_v of minimum width, if any 11: if uu exists then 12: L←∑w assigned to uIv⊆IwMwRukyw+MvRukyvL \leftarrow\sum_{\substack{w\ \mathrm{assigned\ to}\ u\\ I_v\subseteq I_w}} \frac{M_wR_u}{ky_w} + \frac{M_vR_u}{ky_v} 13: if uu exists and L≤1L \le1 then 14: Assign the entire cohort vv to uu. 15: else 16: Select vv as a root, set Rv=yvR_v = y_v, and assign vv to itself. 17: Schedule its service at b+yvb+y_v. At the service time bu+Rub_u + R_u of a root uu: 18: Serve all requests assigned to uu in one batch; retire uu.

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∣/k∈[0,1]\alpha_B = |B \setminus P|/k \in[0,1] for the fraction of capacity used by residual requests in BB. The number of preprocessed requests in BB is at most k(1−αB)k(1-\alpha_B). All residual homes represented in BB lie inside [min⁡r∈Bar,max⁡r∈Bar+2YB][\min_{r \in B} a_r,\max_{r \in 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/k\beta_r = R_u/k; preprocessed requests receive weight zero. We write W=∑rβrW = \sum_r \beta_r for their total weight.

Lemma 3.4. 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/kY_B/k, and there are at most αBk\alpha_B k 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|Q_j|. 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. □

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

MvRukyv≥θ.\frac{M_vR_u}{k 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 3.5. For every feasible offline batch BB,

∑r∈Bγr≤DB+(2+αB/θ)YB.\sum_{r \in B} \gamma_r \le D_B + (2+\alpha_B/\theta)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≤Rukθ≤YBkθ.\gamma_r=\frac{y_v}{M_v}\le\frac{R_u}{k\theta}\le\frac{Y_B}{k\theta}.

There are at most αBk\alpha_B k 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. □

Lemma 3.6. 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 k=16k=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 1.

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 3.4.

An unbounded loss in the certificate. For m≥2m \ge2, take k=2m+1k = 2^{m+1}, b=2mb = 2^m, and ε=2−m\varepsilon= 2^{-m}. Release k/2k/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−ℓ/k=1/22^\ell\cdot2^{m-\ell}/k = 1/2 to the certificate. Thus

∣B∣=2m−1<k,YB=1,DB=1−2−(m−1),∑r∈Bβr=m/2.|B| = 2^m - 1 < k,\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⁡k)\Theta(\log k). 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 2 illustrates the disjoint areas used in Lemma 3.6. The accounting follows ownership: nested selected roots do not repeatedly use one ancestor’s requests.

Figure 2. 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 3.3–3.6, 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 (2), 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−θ).(4)\operatorname{ALG}\leq\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*{(4)}

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_* =18+6\sqrt{3}.

For already scaled-dyadic radii, YB=XBY_B=X_B, and hence (4) proves the C∗C_* bound. For arbitrary radii, YB<2XBY_B<2X_B, proving the 2C∗2C_* 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

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

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

Proof. 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_2 x-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 (4) 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}]\leq\sum_B\left((6+\sqrt{3})D_B+\frac{C_*}{\ln2}X_B\right)\leq\frac{C_*}{\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_* 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.

Arbitrary request sizes

We now allow each request to have an indivisible size srs_r revealed at arrival. A batch of capacity K>0K > 0 must satisfy ∑r∈Qsr≤K\sum_{r\in Q} s_r \le K, where sr∈[0,K]s_r \in[0,K]. Requests cannot be split, and size affects feasibility only: a batch still pays its service cost plus its maximum waiting time. Zero-size requests may therefore have positive cost. Unit sizes with K=kK = k recover the main model. With xr=1x_r = 1, K=1K = 1, and positive sizes, this is bin packing with per-bin maximum delay [23]; that special case admits smaller competitive constants than the guarantees below for arbitrary radii.

Corollary 3.8. The deterministic and randomized guarantees of Theorem 3.2 and Corollary 3.7 hold for arbitrary indivisible sizes, including zero sizes. The deterministic algorithm is polynomial-time for rational input. The randomized algorithm uses polynomially many operations in the ideal-real model specified in § 3. Neither needs a minimum-size assumption. In particular, the deterministic competitive ratio is 36+12336 + 12\sqrt{3}.

Only preprocessing and the units of path load change. Within each newly revealed cohort, serve requests larger than K/2K/2 as singletons. Process the others by Next Fit in a fixed order, closing and serving the current bin when the next request does not fit. Retain the final nonempty bin as the residual cohort, even when its load is exactly KK. Every served bin has load greater than K/2K/2, so its cost is paid by the size-weighted volume bound, with a constant loss.

Let MvM_v now denote the total size of residual cohort vv, rather than its cardinality. Its contribution to the path load of an owner uu is MvRu/(Kyv)M_vR_u/(Ky_v). Integrating this load over the owner’s interval bounds the total assigned size by KK. Thus the same admission rule preserves capacity without splitting a cohort or any request. The light-root argument also uses the same path load; the certificates β\beta and γ\gamma distribute their weights by size. Appendix E gives the weighted proof, including zero-size requests, and the pseudocode. The algorithm requires no optimum bin packing.

Learning-augmented capacitated LAD

§ 3 gives a constant-competitive algorithm without advice. We now seek to follow a good advised schedule more closely while retaining a worst-case guarantee. We use the online revelation of advice and the consistency benchmark of Lu et al. [25] for additive-delay LAD. With capacity, each suggestion must also specify which requests it serves: at time tt, an advice event reveals a service (Q,t)(Q,t) and the identities of its already arrived requests. The algorithm sees no future advice events or total advice cost. The provider may know the full input; only when its advice is revealed is restricted.

As in [25], consistency 1+ϵ1+\epsilon means ALG⁡(I)≤(1+ϵ)cost⁡(ADV⁡)\operatorname{ALG}(I) \le(1+\epsilon)\operatorname{cost}(\operatorname{ADV}) for every complete, capacity-feasible advice stream ADV⁡\operatorname{ADV} on II. Robustness RR requires ALG⁡(I)≤ROPT⁡(I)\operatorname{ALG}(I) \le R\operatorname{OPT}(I) even for inaccurate advice. Invalid references can be ignored and no physical action may violate capacity. Consistency compares with the supplied feasible schedule, even when it is far from optimal.

The new difficulty is accounting for requests left pending when switching between advice and a robust baseline. Under additive delay, waiting costs are charged separately to requests. Under maximum delay, one advice batch may share a waiting cost that the algorithm pays across several batches. Capacity can also force a switch to clear old requests in several services. Charging each clearance to the original advice batch would count its cost repeatedly. We therefore need switching rules that control the pending requests and charges that remain additive across switches. The monitor below gives the following guarantee.

Theorem 4.1. For LADLAD with capacity kk, let BB denote a deterministic RR-competitive online algorithm. For every 0<ε≤10 < \varepsilon\le1, there is a deterministic online algorithm satisfying

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

The first bound holds for every complete, capacity-feasible advice stream ADV⁡\operatorname{ADV} revealed at its service times. The second holds independently of advice quality, including when advice is incomplete. The algorithm needs no future advice partition or total advice cost. For rational input and ε\varepsilon, the overhead is polynomial in the processed input and advice description if BB is polynomially simulable.

With the LADLAD algorithm from § 3 as the baseline, robustness is O(ε−2)O(\varepsilon^{-2}).

The switching idea. The algorithm simulates the advice and the baseline throughout the input. It measures each schedule by the cost already paid plus lower bounds on the service and waiting costs of its pending requests. Geometrically increasing budgets determine which schedule to follow. Advice is preferred whenever its budget permits; a smaller budget for the baseline limits spending away from advice. At a switch, clearing all old pending requests ensures that the new schedule can serve every request still waiting for the algorithm.

The main issue is paying for these clearances while keeping consistency close to one. When leaving advice, the waiting charge is paid by the decrease in its remaining cost after deleting the requests just cleared. Different switches use successive decreases, rather than repeatedly charging an entire advice batch. The baseline budget pays the additional service cost. When returning to advice, the algorithm also clears requests that advice served while the baseline was active; these are charged within the baseline block. This restores the residual-advice comparison at every return.

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),(7)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*{(7)}

where each minimum is over partitions into groups of at most kk 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 kk requests minimizes the sum of group maxima. Indeed, for every z≥0z\ge0 any partition has at least ⌈∣{r:vr>z}∣/k⌉\left\lceil\lvert\{r:v_r>z\}\rvert/k\right\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 4.2. There are polynomial-time procedures that clear PP at time tt with cost at most

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

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

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

Every output batch has at most kk requests.

The ordinary procedure sorts requests by nonincreasing max⁡{xr,wr(t)}\max\{x_r,w_r(t)\} and groups consecutive kk 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 4.2 appear in Appendix § 9.

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).(10)H_X(t) = p_X(t) + S(P_X(t)) + D(P_X(t),t). \tag*{(10)}

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 4.3. 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).(11)S(P) \le p_B(t) + S(P_B(t)) \le H_B(t). \tag*{(11)}

The switching rule

We set

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

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 (9) for A→BA \to B and (8) 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 < \varepsilon \le 1$; continuously simulated advice $A$ and baseline $B$
1: $\eta \leftarrow \varepsilon/2$; $\delta \leftarrow \varepsilon/[4(3 + 2/\varepsilon)]$
2: $S(P) \leftarrow \operatorname{PackValue}(P, x, k)$; $D(P,t) \leftarrow \operatorname{PackValue}(P, t-a, k)$
3: For $Y \in \{A,B\}$ maintain its own pending set $P_Y$ and paid cost $p_Y$.
4: $H_Y(t) \leftarrow p_Y + S(P_Y) + D(P_Y,t)$; maintain physical pending $P$ separately.
5: Serve radius-zero arrivals immediately and remove their identifiers from advice.
6: At the first positive-radius arrival block $J$, admit $J$ to all three queues; set $b \leftarrow 2S(J)$ and active source $X \leftarrow A$ before service events.
7: function $\operatorname{Select}(h_A,h_B,t)$
8: $X_{\mathrm{old}} \leftarrow X$
9: while $h_A \ge b$ and $h_B \ge \delta b$ do
10: $b \leftarrow 2b$
11: if $h_A < b$ then
12: $X \leftarrow A$
13: else
14: $X \leftarrow B$
15: if $X \ne X_{\mathrm{old}}$ then
16: if $X_{\mathrm{old}} = A$ then
17: $\operatorname{Clear}(P,t,\mathit{biased},\eta)$
18: else
19: $\operatorname{Clear}(P,t,\mathit{ordinary},1)$
▷ No cleanup on a same-source level change
20: Define $\operatorname{cap}(A)=b$ and $\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∣/k⌉\lceil|P_X|/k \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.

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

Advice combiner flow diagram

Figure 3. 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 4.4. 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.

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∣/k⌉t+[\operatorname{cap}(X)-H_X(t)]/\lceil|P_X|/k\rceil; otherwise cancel it.

  2. Continue both virtual schedules without restarting either one.

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.(13)\Phi(Z) = \sum_j c(G_j \setminus Z,T_j), \qquad c(\varnothing,T_j)=0. \tag*{(13)}

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 4.5. 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.(14)F_A + \sum_e D(P_e,t_e) \le C_A. \tag*{(14)}

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 (13) by its actual service cost.

For an A→BA \to B change at time tt, we write P=PeP=P_e. By Lemma 4.4, 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. □\square

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 4.4.

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

Residual charging diagrams

Figure 4. 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 § 9. 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+.(15)S(P_e) \le H_B^{\mathrm{post}} < \delta b_e^+. \tag*{(15)}

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 4.6. For an AA block,

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

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

Lemma 4.7. 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.(17)\sum_{e\in\mathcal{E}} b_e^+\le2C_A,\qquad \sum_{J:\,B\ \mathrm{block}} b_J\le2C_A. \tag*{(17)}

For arbitrary advice, the largest level obeys

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

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 4.5 pays for followed advice services and the waiting part of leaving AA. The service part is bounded by (15), and Lemma 4.6 pays for complete BB blocks. Using the two geometric sums in Lemma 4.7 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} \operatorname{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\text{ 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 (16) over AA blocks, bound their additional service-cost cleanup terms by (15), 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.\operatorname{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 (6). Completion and the polynomial-time implementation are verified in Appendix § 9.

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 4.8. Fix k≥1k\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 kk requests it must satisfy

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

Consequently, a robustness bound uniform in kk 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 § 9; the optimal dependence on ε\varepsilon is open.

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.

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?

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 kk are pending, it serves the kk 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 5 records this rule. All services occur at the current event time. A stale timer is replaced whenever its buffer changes.

Algorithm 5 The fixed-location full-or-age rule
1: function FullOrAge(k, w)
2:     Maintain an arrival-ordered queue Q.
3:     On an arrival block, append its requests to Q in a fixed tie order.
4:     while |Q| ≥ k do
5:         Serve and remove the first k requests.
6:     After arrival actions, if Q ≠ ∅ and its oldest age is at least w, serve all of Q and empty it.
7:     Otherwise schedule the nonempty queue’s timer at its oldest arrival plus w.
8: A timer serves the entire nonempty queue. If w = 0, serve arrivals immediately.

Lemma A.1 (Greedy short prefixes). For requests at one location, call a batch short if it has at most kk 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⁡{k,∣{r:ar≤a+w}∣}q = \min\{k, |\{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 kk, 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 kk 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 kk 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 kk 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 k≥2k \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),(3,4),…,(N−1,N)(1,2),(3,4),\ldots,(N-1,N) at their second arrivals. The second serves requests 1,N1,N singly and serves (2,3),(4,5),…,(N−2,N−1)(2,3),(4,5),\ldots,(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 kk, every randomized online algorithm has ratio at least

k1+(k−1)(1−e−1)\frac{k}{1+(k-1)(1-e^{-1})}

against an oblivious adversary, already at one location. Consequently a competitive constant uniform in kk 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 gi=ai+1−aig_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 gig_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⁡{gi,1}.(20)\operatorname{OPT} = 1 + \sum_{i<n} \min\{g_i,1\}. \tag*{(20)}

For the lower bound, the input has n=kn = k 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}[\operatorname{ALG}] \ge n, whereas (A.1) gives E[OPT⁡]=1+(n−1)(1−e−1)\mathbb{E}[\operatorname{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 kk grow gives the uniform bound. For arbitrary sizes, nn requests of size 1/n1/n give the same bound as nn grows. □\square

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+Δ,kx}.\sum_{x \le R} \min\{x+\Delta,n_xx\} \le\sum_{\substack{x \le R\\x\ \mathrm{dyadic}}} \min\{x+\Delta,kx\}.

If Δ=0\Delta= 0, this sum is at most 2R2R. Otherwise the radii x≤Δ/kx \le\Delta/k contribute at most 2Δ2\Delta by geometric summation. There are at most ⌈log⁡2k⌉+1\lceil\log_2 k\rceil+ 1 dyadic radii in (Δ/k,Δ](\Delta/k,\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⁡2k⌉+4)(R+Δ)(2\lceil\log_2 k\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. □\square

Proof of capacity transfer for additive delay and deadlines

We derive the capacity-transfer bounds discussed in Section 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 kk. An edge used by ne>0n_e > 0 requests appears in an expected 1+(ne−1)/k1 + (n_e - 1)/k pieces. Summing over edges bounds the service cost by

(1−1k)f(B)+1k∑r∈Bpr\left(1 - \frac{1}{k}\right)f(B) + \frac{1}{k}\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 k<∣B∣k < |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/k\alpha= 1 - 1/k and write V=∑rpr/kV = \sum_r p_r/k for capacity kk, 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 kk. 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.

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 4.2. For (8), the procedure sorts requests by qr=max⁡{xr,wr(t)}q_r = \max\{x_r,w_r(t)\} and groups consecutive kk requests. For every zz, the number of groups whose maximum qq exceeds zz is

⌈∣{r:qr>z}∣k⌉≤⌈∣{r:xr>z}∣k⌉+⌈∣{r:wr(t)>z}∣k⌉\left\lceil\frac{|\{r:q_r>z\}|}{k}\right\rceil \le \left\lceil\frac{|\{r:x_r>z\}|}{k}\right\rceil + \left\lceil\frac{|\{r:w_r(t)>z\}|}{k}\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 (9), 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 kk 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 (9).



Algorithm 6 Clearing pending requests at an advice switch
1: function SortPack($P$, $v$, $k$)
2: Sort $P$ by nonincreasing $v_r$, breaking ties by request identity.
3: return consecutive groups of $k$ requests, with a shorter last group if needed
4: function PackValue($P$, $v$, $k$)
5: return $\displaystyle\sum_{G\in\operatorname{SortPack}(P,v,k)}\max_{r\in G}v_r$
6: function Clear($P$, $t$, mode, $\eta$)
7: $w_r \gets t-a_r$ for $r\in P$
8: if mode = ordinary then
9: $\Pi \gets \operatorname{SortPack}(P,\max\{x,w\},k)$
10: else
11: $L \gets \{r\in P:x_r\le\eta w_r\}$
12: $\Pi \gets \operatorname{SortPack}(L,w,k)\cup\operatorname{SortPack}(P\setminus L,x,k)$
13: Serve every nonempty $G\in\Pi$ at $t$; remove its members from physical pending.

Algorithm 6 implements the two clearance procedures.

Proof of Lemma 4.3. 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 (11), 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 4.6. 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 (16). For BB, apply (8) 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 4.7. 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 (17) 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 (18). 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 (18) 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∣/k⌉\lceil|P_X|/k\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 4.8. 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 kk. 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<kxiX = \sum_{i<k} x_i. On the input stopped after k−1k-1 requests, advice costs k−1k-1, while the algorithm costs at least (k−1)+X(k-1)+X. Since future advice is not revealed, its execution through these services is identical to that on the full input. Hence X≤ε(k−1)X \le\varepsilon(k-1). On the full input, online cost is at least k+Xk+X. All requests fit together, and hence serving them at the final arrival costs at most 1+X+Δ1+X+\Delta, where Δ=∑i<kδi\Delta= \sum_{i<k}\delta_i. For Δ<k−1\Delta< k-1, the function (k+X)/(1+X+Δ)(k+X)/(1+X+\Delta) decreases in XX. Letting Δ↓0\Delta\downarrow0 proves (19); k=1k=1 is immediate. Letting k→∞k \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.9.

Proof of Corollary 3.8. Under the preprocessing of § 3.9, 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

ALG⁡pre≤4K∑r∈Psryr\operatorname{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.9, the same integration argument gives ∑r assigned to asr≤K\sum_{r\ \text{assigned to }a}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 3.4 and 3.5 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 3.6 charges each request at most βr/(1−θ)\beta_r/(1-\theta). Combining these bounds with preprocessing gives exactly (4). 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 7 replaces only the cohort preprocessing and the load units in Algorithm 2. It retains the final nonempty bin even when its load is exactly KK.

Algorithm 7 Weighted cohort preprocessing for the path-load algorithm

Require: Home cohort QQ of width yy, revealed at bb; capacity KK

  1. Serve every r∈Qr \in Q with sr>K/2s_r > K/2 as a singleton at bb.

  2. T←∅T \leftarrow\varnothing

  3. for remaining requests rr in a fixed order do

  4. &nbsp;&nbsp;&nbsp;&nbsp;if ∑q∈Tsq+sr>K\sum_{q \in T} s_q + s_r > K then

  5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Serve TT at bb; T←∅T \leftarrow\varnothing.

  6. &nbsp;&nbsp;&nbsp;&nbsp;T←T∪{r}T \leftarrow T \cup\{r\}

  7. if T≠∅T \ne\varnothing then

  8. &nbsp;&nbsp;&nbsp;&nbsp;Pass TT as one residual cohort to Algorithm 2.

  9. &nbsp;&nbsp;&nbsp;&nbsp;Use Mv=∑r∈TsrM_v = \sum_{r \in T} s_r and replace kk by KK 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.

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, Lukasz Jeż, Dorian Nognenq, 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, Lukasz 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.
  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.
  23. [23]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online bin packing with per-bin maximum delay. arXiv:2609.29589, 2026.
  24. [24]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online covering with maximum delay under subadditive service costs. arXiv:2609.32675, 2026.
  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.
  26. [26]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Online multi-level aggregation with per-batch maximum delay. arXiv:2608.06796, 2026.
  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.
  28. [28]Jeremy McMahan. A D-competitive algorithm for the multilevel aggregation problem with deadlines. arXiv:2108.04422, 2021.
  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.
  33. [33]Steven S. Seiden. A guessing game and randomized online algorithms. In Proc. STOC, pages 592–601, 2000.
  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.
  36. [36]Jingyang Zhao and Mingyu Xiao. Improved approximation algorithms for capacitated vehicle routing with fixed capacity. In Proc. MFCS, pages 93:1–93:19, 2025.

Paper details

vlnc:W_sz55z4jz
Version
v1 · 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

Not recorded for this paper

View statement
Looking for related papers…
Contents