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 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 . 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 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 -consistency against every complete feasible advice schedule and -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 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 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 for capacity . For radii on a fixed scaled dyadic grid, the competitive ratio is . A random common scale offset gives an expected competitive ratio of 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 -competitive baseline. For , the resulting algorithm is -consistent against every complete feasible advice stream and -robust. Our LAD baseline gives -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 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 randomly against an oblivious adversary. Their framework requires every request set to be realizable by one service. In LAD, 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 and radius corresponds to an interval of weight . A feasible batch contains at most intervals with a common intersection and costs their maximum weight. The problem is strongly NP-hard already for and admits a PTAS for every fixed . 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 has an arrival time and a distance from the origin on a rooted half-line, both revealed at arrival. We call its radius. Requests remain distinct even when they arrive at the same location and time. The capacity is a known integer . A service completes a nonempty set of at most pending requests at time . Its service and total costs are
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 for its total cost on input and for the minimum cost of a feasible offline schedule. A deterministic algorithm is -competitive if for every input, with no additive constant. Unless stated otherwise, we assume and positive radii: for , 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 -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 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 , it independently runs the full-or-age algorithm with setup : whenever at least requests are pending, it serves the oldest; otherwise, it serves all pending requests when the oldest reaches age . 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
Serve zero-radius requests immediately for free.
Assign every other request to its rounded radius .
At each rounded radius , run FullOrAge from Algorithm 5.
Execute the resulting services independently; do not merge groups.
Proposition 3.1. For , the independent-class algorithm is -competitive.
The proof of the upper bound appears in Appendix § 7.
A matching lower-bound instance. Let and . For each , set and release one request at radius at each time , where . The total number of requests is
At radius , every request reaches age before the next request in its class arrives. The algorithm therefore serves it alone at time , paying . Each class contributes , so .
Offline can serve all requests in one batch at the last arrival time . This batch respects capacity, has maximum radius and maximum waiting time , and costs . Consequently,
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 , collect the requests arriving in , where is a multiple of . At time , this group is completely known. Serve full batches of requests immediately and retain the remainder as a single group, called a cohort. A full batch costs at most : its service cost is and its maximum delay is at most . These batches are paid for by the volume lower bound
Indeed, a batch’s largest radius is at least the sum of its requests’ radii divided by .
Give the remaining cohort the home interval . It could be served at the right endpoint for cost at most . 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 . A cohort of requests with home length reserves units of area under this interval. Spread this area uniformly over its own home. Its load there is
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 . Since every assigned request contributes area , at most 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 . Two requests of radius arrive at time ; two of radius arrive at time ; and at time one request of radius and one of radius arrive. Figure 1 follows all six requests. No full batch is removed in preprocessing.

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 , and its two requests contribute load . The radius-4 cohort has home and adds load there. It is accepted. At time 10, the radius-2 request reveals its home . Its prospective load is , taking the total on this home to . 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 .
At time 12, the last radius-4 request reveals home . This home is disjoint from , and its load test is only . It joins the first root. The resulting five-request batch is served at time 16, for cost . The algorithm’s total cost is therefore 30.
Offline can serve all six requests at time 8, for cost . 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 already present throughout the rejected home . The area under this old load is , enough to pay its length 2 within a constant factor. More generally, a failed test means that either the incoming cohort contributes at least , or the old load exceeds 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 and whose arrival span is . Its cost is at least . Requests with owners of length at most 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 .
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 whose competitive ratio is at most . For radii on a fixed scaled dyadic grid, the ratio is at most
These deterministic guarantees hold also for adaptively generated inputs.
Strict time rounding and local preprocessing
We write for the arrival time of request and for its radius. Each batch contains at most requests. For a fixed , the radius grid is . The deterministic algorithm uses ; we keep the scale explicit for the randomized extension. The algorithm rounds upward to the smallest grid value and gives the virtual arrival
Thus . Its home interval is . Any two home intervals are disjoint or one contains the other. At time , the full cohort with home consists of the requests of rounded radius that actually arrived in . The cohort is therefore known from the strict past. An arrival at time cannot change it, even when arrivals depend on earlier service decisions.
At a cohort’s virtual arrival, the algorithm serves full groups of 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 has actual waiting at most and radius at most . Its cost is at most , and hence at most times its cardinality. If denotes the set of preprocessed requests, then
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 for a nonempty residual cohort, for its home, and 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 arrives, let denote its nearest selected strict ancestor, if one exists, and write . To decide whether can join , the algorithm distributes a load over . Its integral is , the interval length reserved for these requests. Since earlier homes meeting contain it, their contributions are constant throughout . Admitting would give total load
If exists and , the algorithm assigns to . Otherwise, becomes a new root and owns its own cohort (lines 14–16 of Algorithm 2). A root serves all its assigned requests at time . 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 . 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 , define
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 . Once a new selected root appears on the chain, subsequent descendants use that nearer root. Consequently almost everywhere. Integration gives
which proves feasibility without splitting any request.
If has home , then and . Its actual arrival satisfies . At time , its waiting is at most and its radius is at most . The root batch therefore costs at most . 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 ; one fixed scale ; deterministic tie orders Use for the deterministic version; for Corollary 3.7, draw uniformly from once and set .
1: Initially no requests, cohorts, or selected roots are stored. On arrival of request at : 2: ; 3: Store in the cohort with home . At a virtual arrival time : 4: for nonempty homes in decreasing do 5: the requests stored for this home 6: while do 7: Serve the first requests of at and remove them from . 8: if then 9: Create cohort with , , and . 10: the selected strict ancestor of of minimum width, if any 11: if exists then 12: 13: if exists and then 14: Assign the entire cohort to . 15: else 16: Select as a root, set , and assign to itself. 17: Schedule its service at . At the service time of a root : 18: Serve all requests assigned to in one batch; retire .
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 can be served at its latest arrival, giving minimum cost , where
We also write for the fraction of capacity used by residual requests in . The number of preprocessed requests in is at most . All residual homes represented in lie inside . Thus every disjoint collection of such homes has total length at most . This observation compares virtual homes directly with the original arrival span.
Each residual request assigned to receives weight ; preprocessed requests receive weight zero. We write for their total weight.
Lemma 3.4. For every feasible offline batch ,
Proof. Let be the inclusion-maximal distinct residual homes represented in . They are disjoint, with total length at most . We split the charge according to whether a request’s owner is contained in its maximal home or strictly contains . The first group is bounded by the number of requests in ; the second will be bounded by integrating load over the disjoint .
Owners of the first kind have width at most . Each of their requests therefore has weight at most , and there are at most residual requests in . Their total weight is at most .
All requests of the second kind within a given 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 was therefore known when was processed. Let be its nearest selected strict ancestor, if one exists. A descendant home can be assigned above only to : any selected root between that home and would instead become its nearest candidate owner. Assignments are never revised, so roots selected later inside do not change earlier owners. If itself is selected, or if does not exist, the second group is empty. Otherwise, the weight of this group is at most . Indeed, integrating the density of a whole assigned home contained in gives exactly its total weight; selecting only part of that cohort reduces the weight. Summing over bounds the second group by . Adding the first group’s gives , as claimed. □
An owner may occur in several offline batches. The comparisons remain additive because each batch sums only its own requests’ weights; the integral bounds these weights without assigning a new charge to the owner each time.
For the analysis, we fix . A selected root is heavy if it has no selected ancestor or, writing for its parent selected root, if
All other roots are light. Each request in the cohort that created a heavy root receives weight ; all other requests receive weight zero. Every residual cohort is nonempty, and hence . The total weight equals the total width of heavy roots.
Lemma 3.5. For every feasible offline batch ,
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 are disjoint. Their total length is at most , and their represented weight is at most this length, even when contains only part of a cohort.
For a nonmaximal represented heavy root , some represented heavy ancestor exists. The parent selected root of lies in , and hence . Its heavy inequality gives
There are at most such requests, so the nonmaximal roots contribute at most . Together with the maximal roots’ contribution , this gives the claimed bound. □
Lemma 3.6. The sum of the widths of light roots is at most .
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 denote a light immediate child root of . Its own prospective term is below , but its admission failed. The already assigned ancestor terms therefore sum to more than . Every such term contributes throughout and remains in the final density . Thus
Immediate child-root intervals of are disjoint. Summing over light children and parents yields
More explicitly, a request assigned to pays a light child of the amount
Its total contribution is at most by disjointness. A grandchild of 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 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 . At time , release eight requests at each radius , , and , where . At virtual time , they create roots with homes , , and . Each starts with load . Every smaller seed cohort is rejected by all larger roots, since its prospective load is at least one before adding the existing load.
Inside , create one request for every home in the following three levels. A request with home has radius and arrives at .
| level | home width | number of homes | owner width | total |
| 0 | 1 | 1 | 8 | 1/2 |
| 1 | 1/2 | 2 | 4 | 1/2 |
| 2 | 1/4 | 4 | 2 | 1/2 |
Table 1.
The first request adds load to the largest root, filling its load throughout . Each half-width home is therefore rejected there, but adds load 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 use three different owners strictly above , violating the unique-owner property in Lemma 3.4.
An unbounded loss in the certificate. For , take , , and . Release seed requests at each radius at time . They create roots starting at , each with initial load . Let consist of one additional request for each dyadic home in at levels :
Its radius is and its arrival is the left endpoint minus . No cohort reaches capacity. As in the three-level example, earlier levels fill each larger root on , while disjoint homes at level fill the remaining load of the root of width . Each level contributes to the certificate. Thus
Serving at its last arrival costs , so its weight exceeds its batch cost by . 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 , so failed admission certifies 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 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 and , respectively. The factor three comes from the root-batch cost bound . Inside an offline batch , preprocessing contributes at most by (2), while the two certificates bound the residual charges. Keeping 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
The coefficient of is positive. Maximizing over yields the batchwise comparison
The capacity constraint in this calculation belongs to the offline batch . Its preprocessed and residual requests occupy disjoint portions of that capacity, although the online algorithm may serve them in different batches.
The choice minimizes and gives
For already scaled-dyadic radii, , and hence (4) proves the bound. For arbitrary radii, , proving the bound of Theorem 3.2. The threshold 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 admits a randomized online algorithm with expected competitive ratio
Proof. The algorithm draws uniformly from once, sets , and uses this scaled dyadic grid for both radii and time. For any fixed , its rounded radius is
We fix an input independent of and an optimal partition of the original requests. The common monotone rounding map gives . Applying (4) to this same partition for every and taking expectations gives
which proves the corollary by linearity of expectation.
The expectation uses an input fixed independently of the scale. For adaptive inputs, the deterministic 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 revealed at arrival. A batch of capacity must satisfy , where . 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 recover the main model. With , , 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 .
Only preprocessing and the units of path load change. Within each newly revealed cohort, serve requests larger than 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 . Every served bin has load greater than , so its cost is paid by the size-weighted volume bound, with a constant loss.
Let now denote the total size of residual cohort , rather than its cardinality. Its contribution to the path load of an owner is . Integrating this load over the owner’s interval bounds the total assigned size by . 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 and 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 , an advice event reveals a service 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 means for every complete, capacity-feasible advice stream on . Robustness requires 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 with capacity , let denote a deterministic -competitive online algorithm. For every , there is a deterministic online algorithm satisfying
The first bound holds for every complete, capacity-feasible advice stream 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 , the overhead is polynomial in the processed input and advice description if is polynomially simulable.
With the algorithm from § 3 as the baseline, robustness is .
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 at time , we write and define
where each minimum is over partitions into groups of at most requests. The two minimizing partitions may differ: ignores waiting, and ignores distance. Nevertheless, any feasible partition pays at least in service cost and in current waiting cost, so their sum is a lower bound on clearing . Both values are zero on the empty set. For nonnegative weights , sorting them in nonincreasing order and grouping consecutive requests minimizes the sum of group maxima. Indeed, for every any partition has at least groups of maximum weight greater than , and the sorted partition attains all these bounds. Integration over proves optimality. Thus and are exactly computable by sorting; they are also monotone under taking subsets.
Lemma 4.2. There are polynomial-time procedures that clear at time with cost at most
and, for any , with cost at most
Every output batch has at most requests.
The ordinary procedure sorts requests by nonincreasing and groups consecutive requests. The biased procedure separates from its complement, sorting 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 and the advice schedule . A revealed advice proposal is executed in the simulation of . Neither simulation is restarted at a switch. We call their states virtual, and use physical for the services actually executed by our algorithm. Let and denote the paid cost and pending set of , respectively. Its score is
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 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 is nondecreasing. If is complete and feasible, then for all . Moreover, for any set of already arrived requests,
The switching rule
We set
At the first positive-radius arrival block , the algorithm initializes and uses the levels . The level never decreases. At level , advice is eligible when , and the baseline is eligible when . The algorithm prefers whenever it is eligible. If neither is eligible, it doubles until one becomes eligible. Initially is eligible because all requests in 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 and (8) for (lines 17 and 19 of Algorithm 3). The latter clearance includes requests that virtual advice served while 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 , 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.

Figure 3. The advice combiner separates virtual histories from physical service. Here is the physical pending set, and the displayed packing costs are evaluated on the old set cleared at a switch. Returning to 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 block, the physical pending set is a subset of . 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 at time , after initialization:
for
if then
▷ Cleanup sees , not
Add to ; then process the time- virtual services.
Virtual service , in fixed order at ties:
If , keep only distinct identifiers of in ; discard empty or infeasible proposals.
for the other source ;
if and then
▷ Before committing this virtual service
if and then
Serve physically if nonempty; remove it from .
; ▷ Always commit the virtual event
Waiting timer, after arrivals and virtual services at time :
if then
After each event or selection:
If , set the next cap timer to ; otherwise cancel it.
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 . For consistency, we need to pay for followed advice services and for the waiting part of each clearance. Both payments come from deleting physically served requests from the original advice batches. For the set of physically served request identifiers, the remaining advice cost is
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 .
Lemma 4.5. Let denote the total cost of physical services following source . At each change , let denote the old physical pending set cleared at time . Then
Proof. We show that each followed advice service reduces by its physical cost, and each clearance reduces by at least the corresponding value. Since starts at and never increases, these decreases can be summed.
At a followed advice service , its remaining identifiers are exactly its physical restriction. Deleting them reduces the th summand of (13) by its actual service cost.
For an change at time , we write . By Lemma 4.4, every request in is still pending in virtual advice. Thus each affected original batch has . We write . After deleting , any surviving identifier in has release at least : all earlier arrivals were either served physically before this change or belong to . New arrivals that trigger the change have release exactly .
If an affected batch remains nonempty, its oldest surviving release therefore advances to at least , reducing its delay cost by at least . Its service cost does not increase. If the batch becomes empty, its entire remaining cost is at least the same amount, since . The nonempty form a capacity-feasible partition of , and hence the total potential drop is at least .
All other physical actions, including cleanup, cause additional nonnegative potential drops. Summing the charged drops proves the lemma. In particular, repeated charges involving one original advice batch use successive decreases of its residual cost, never its original cost again.
During a 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 -block bound below. Before returning to , the full cleanup removes all such identifiers and restores the inclusion in Lemma 4.4.
Figure 4 shows the waiting credit at one exit and how credits telescope.

Figure 4. Residual charging pays for elapsed waiting only once. In (a), the original advice batch is served at ; after all old physical pending requests are deleted, its oldest surviving arrival is at least . 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 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 exit and for complete 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 denote the set of changes, and let denote the newly selected level at change . The service-cost certificate gives
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 , let denote its last occupied level and the cost of its followed physical services, excluding exit cleanup. If the block ends at a switch, and denote the old pending set and exit time. For a final block without exit cleanup, we use below.
Lemma 4.6. For an block,
For a block, the followed services together with its exit cleanup cost at most .
Lemma 4.7. At a fixed level there is at most one block and one block. The last levels of distinct blocks of the same source are distinct, as are the newly selected levels at changes.
If advice is complete and feasible, then
For arbitrary advice, the largest level obeys
and the sum of all opened levels is at most .
Proof of Theorem 4.1. All physical batches are feasible by construction. For consistency, we partition physical cost into followed services, cleanups, and complete blocks including their exit cleanups. Lemma 4.5 pays for followed advice services and the waiting part of leaving . The service part is bounded by (15), and Lemma 4.6 pays for complete blocks. Using the two geometric sums in Lemma 4.7 gives
The residual-advice bound controls the first two terms by . The -block term includes the cost of requests already served by virtual advice; these require no further advice charge.
For robustness, we sum (16) over blocks, bound their additional service-cost cleanup terms by (15), and apply the -block bound. These comparisons use no bound on . The last levels of blocks, the last levels of blocks, and the newly selected levels at switches each form a sequence without repetition. Bounding each sum by gives
Since , this is (6). Completion and the polynomial-time implementation are verified in Appendix § 9.
A lower bound on robustness
The dependence on 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 and . For maximum delay at one location, suppose a deterministic algorithm is -consistent against every feasible online-revealed advice stream and -robust. Already on inputs with at most requests it must satisfy
Consequently, a robustness bound uniform in must satisfy for ; at no finite such bound is possible.
The proof is in Appendix § 9; the optimal dependence on 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 , while the deterministic lower bound is 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 , a batch costs plus its maximum age. The algorithm keeps pending requests in arrival order. Whenever at least are pending, it serves the oldest and repeats if necessary. Otherwise, it serves the entire pending set when its oldest request reaches age . A full-batch trigger has priority over a simultaneous timer. Every resulting batch costs at most . 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 members and arrival span at most . The greedy partition into maximal arrival-ordered short prefixes minimizes the number of short batches, even when nonconsecutive groups are allowed.
Proof. Let denote the earliest arrival, and let denote the first requests in arrival order. In any short partition, the batch containing the first request has and all its arrivals in .
For each request , we choose a distinct request and swap into the batch containing . There are enough such because . Requests of precede all displaced requests in arrival order. Thus an inserted arrives no earlier than the removed , and no later than . In a receiving batch with original earliest arrival , the new earliest arrival does not decrease, and every inserted arrival is at most . Its span remains at most and its cardinality does not increase. We move any remaining requests of into , deleting them from their old batches. The batch has become exactly , and no additional batch has been created. Empty batches are deleted.
We remove 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 , full-or-age- is 2-competitive for TCP.
Proof. Its batches are exactly the maximal short prefixes: a prefix ends when it reaches cardinality or when the first request’s age reaches . Boundary arrivals are included before a timer is processed. Let denote the number of algorithm batches. We consider any offline batch of at most requests, with arrival span . Its members are divided into greedy prefixes of span at most , without a cardinality restriction; each piece still has at most members. If there are pieces, consecutive first arrivals differ by more than , and hence . For the bound is immediate. Thus its pieces satisfy , no larger than that comparison batch’s actual cost. Applying this to all comparison batches gives a feasible short partition with number satisfying . Lemma A.1 gives . Hence .
A tight deterministic lower bound
Theorem A.3. For every fixed , every deterministic algorithm for capacitated TCP acknowledgment with maximum delay has competitive ratio at least two.
Proof. We fix setup cost and an even integer . The adversary releases the first request at . After the algorithm serves request at , request arrives at , where . If the algorithm never serves the unique pending request, the adversary ends the input. Otherwise, we write and . Every online batch is a singleton, and hence
We compare the algorithm with two offline schedules. The first serves the pairs at their second arrivals. The second serves requests singly and serves at their second arrivals. Their costs satisfy
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 ,
For fixed , make arbitrarily small, and then let even 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 , every randomized online algorithm has ratio at least
against an oblivious adversary, already at one location. Consequently a competitive constant uniform in is at least . 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 for successive arrival gaps. A normalized algorithm cuts a gap at a timeout if no arrival intervenes. A cut contributes to its total cost; an uncut gap contributes . The final contribution is . 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
For the lower bound, the input has requests, starts at zero, and has 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 is independent of the next gap . For every the expected gap contribution is
The final contribution is at least one, and hence , whereas (A.1) gives . A guarantee on every fixed input must also hold after averaging over this independent distribution, proving the displayed ratio. Letting grow gives the uniform bound. For arbitrary sizes, requests of size give the same bound as grows.
Analysis of the independent-class baseline
Section 3.1 defines the algorithm and gives its matching lower-bound instance. Here we prove the upper bound.
Proof of Proposition 3.1. Fix an offline batch with maximum rounded radius and arrival span . If it contains requests of radius , its restriction can be served together at its last arrival for at most , or as singletons at their arrivals for cost . Each restriction fits in one batch, giving total cost at most
If , this sum is at most . Otherwise the radii contribute at most by geometric summation. There are at most dyadic radii in , each contributing at most . Radii contribute at most . The sum is at most . Applying these restrictions to all offline batches gives a feasible comparison schedule for each class. The factor-two TCP guarantee from Proposition A.2 and the factor-two radius rounding therefore give the claimed competitive ratio.
Proof of capacity transfer for additive delay and deadlines
We derive the capacity-transfer bounds discussed in Section 1.1 for additive waiting costs and deadlines. For a rooted-tree batch , let be the length of request ’s root path. Order requests by a depth-first traversal and cut this order at a uniformly chosen residue modulo . An edge used by requests appears in an expected pieces. Summing over edges bounds the service cost by
For sizes normalized to capacity one, serve requests larger than separately. Group the others by their cumulative start positions in shifted intervals of length . Each group fits, and an edge is used by at most groups in expectation, where contains its small requests. Large requests cost at most twice their volume charge. The resulting bound is . 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 unit offsets. For arbitrary sizes, the partition changes only when a shifted boundary crosses a cumulative start position, giving at most breakpoints.
Let be the service and additive waiting costs of the virtual schedule. Set and write for capacity , or for sizes. Every feasible batch pays at least its volume charge, so for any capacitated comparator with service cost and waiting cost . Keeping all service times therefore gives
respectively. An uncapacitated ratio immediately yields competitive ratios and , respectively. With deadlines, , giving for capacity . For additive waiting, run the baseline with service costs scaled by , whenever it supports this scaling:
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 and groups consecutive requests. For every , the number of groups whose maximum exceeds is
Integrating bounds the sum of group maxima of by . Each actual batch costs at most twice its maximum .
For (9), let denote the set . The procedure packs by nonincreasing age and by nonincreasing radius, using groups of size at most in both cases. On , the maximum radius of a group is at most times its maximum age. On the complement, its maximum age is at most times its maximum radius. The resulting cost is at most , 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 gives
The increase in therefore pays for the total decrease of . To bound , we restrict all future services of to . 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 .
For (11), we partition using restrictions of the past services of , together with a partition of minimizing service cost. Past service costs are at most , and restriction cannot increase them. This proves the bound even when contains requests that has already served.
Block budgets and geometric sums
Proof of Lemma 4.6. Restrictions of source services cannot increase cost, and hence 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 and . For , these facts bound by , proving (16). For , apply (8) and bound paid cost plus twice by twice the old cap . The same bounds hold without exit cleanup for the final block.
Proof of Lemma 4.7. Once is ineligible at a level, monotonicity of prevents it from becoming eligible there again. Thus 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 , preference for implies . This remains true for the last level of a block: each same-source level increase again tests first. Each sum in (17) is therefore a sum of distinct dyadic levels at most , and is at most . They are two separate sums and will have separate coefficients in the cost bound.
Initially . Every subsequent level is twice a level where both eligibility tests failed, and hence at that failed level. Since and , 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, is finite, and hence (18) permits only finitely many levels and source changes. A final block completes because does. A final block with a request pending forever would have unbounded , 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 , ages have a fixed order and is affine with slope . 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 , the number of levels and the arithmetic overhead are polynomial whenever 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 , the adversary waits before releasing request , again with immediate singleton advice. The construction stops after request . Consistency forces the algorithm to serve each request even if no others arrive.
Let denote the wait of request , and write . On the input stopped after requests, advice costs , while the algorithm costs at least . Since future advice is not revealed, its execution through these services is identical to that on the full input. Hence . On the full input, online cost is at least . All requests fit together, and hence serving them at the final arrival costs at most , where . For , the function decreases in . Letting proves (19); is immediate. Letting 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 , since the rejected item has size at most . Large-item singleton batches also have load greater than . Each preprocessed batch at radius costs at most . If is the set of preprocessed requests, then
The residual cohort has total size at most , even if its cardinality is arbitrarily large. For the weighted path load defined in § 3.9, the same integration argument gives ; whole cohorts, and hence indivisible requests, remain intact. Service times and the bound are unchanged. The weighted certificates are
for an own-cohort request of a heavy root .
All other requests receive zero weight. If a heavy root has , we assign its whole weight 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 , we write . Its preprocessed mass is at most . The proofs of Lemmas 3.4 and 3.5 now give
Indeed, the integral over each maximal represented home is unchanged; the remaining terms are bounded by the total size in place of a request count. Immediate child-root intervals are still disjoint, and hence Lemma 3.6 charges each request at most . 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 .
Algorithm 7 Weighted cohort preprocessing for the path-load algorithm
Require: Home cohort of width , revealed at ; capacity
Serve every with as a singleton at .
for remaining requests in a fixed order do
if then
Serve at ; .
if then
Pass as one residual cohort to Algorithm 2.
Use and replace by in every path-load term.
Leave assignments, ancestor selection, and root service times unchanged.
Retain a nonempty zero-load residual cohort; nonemptiness is not a load test.
References
- [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]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]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]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]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]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]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]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]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]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]José R. Correa and Nicole Megow. Clique partitioning with value-monotone submodular cost. Discrete Optim., 15:26–36, 2015.DOI
- [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]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]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]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]Dev Joneja. The joint replenishment problem: new heuristics and worst case performance bounds. Oper. Res., 38(4):711–723, 1990.DOI
- [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]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]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]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]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]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]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online bin packing with per-bin maximum delay. arXiv:2609.29589, 2026.
- [24]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online covering with maximum delay under subadditive service costs. arXiv:2609.32675, 2026.
- [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]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Online multi-level aggregation with per-batch maximum delay. arXiv:2608.06796, 2026.
- [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]Jeremy McMahan. A D-competitive algorithm for the multilevel aggregation problem with deadlines. arXiv:2108.04422, 2021.
- [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]Tim Nonner. Capacitated max-batching with interval graph compatibilities. Theor. Comput. Sci., 613:79–93, 2016.
- [31]Runtian Ren and Xueyan Tang. Busy-time scheduling on heterogeneous machines. In Proc. IPDPS, pages 306–315, 2020.DOI
- [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]Steven S. Seiden. A guessing game and randomized online algorithms. In Proc. STOC, pages 592–601, 2000.
- [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]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]Jingyang Zhao and Mingyu Xiao. Improved approximation algorithms for capacitated vehicle routing with fixed capacity. In Proc. MFCS, pages 93:1–93:19, 2025.
