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. Controlled synthetic experiments with 9,180 exact-rational monitor runs illustrate both the benefit of optimal advice and the delayed fallback caused by the stated conservative constants. We provide all inputs, outcomes, and reproducibility code; the experiments do not claim performance on learned predictions or large-scale demand traces.
Introduction
Sending an acknowledgment, replenishing several types of goods, and serving requests along a common route all allow several requests to share one service cost. Waiting for more requests can reduce that cost, but also delays the requests already present. This tradeoff has been studied in TCP acknowledgment [12, 33, 18], joint replenishment (JRP) [1, 15, 16, 10, 5], and control-message aggregation [19, 8, 6]. Multi-level aggregation (MLA) extends these problems to rooted trees, with algorithms for additive waiting costs and deadlines [3, 4, 9, 2, 28, 22] and a stochastic-arrival variant [27].
Under per-batch maximum delay, each service pays its service cost plus the waiting time of its oldest request, and the objective sums these costs over all services. Lu et al. Lu et al. [26] study this objective for uncapacitated multi-level aggregation on rooted trees. They obtain optimal competitive ratios of 2 deterministically and 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.5.
We also study capacitated LAD in the learning-augmented model. An algorithm receives advice only when a proposed service is due. We combine this advice with any deterministic -competitive baseline. For , the resulting algorithm is -consistent against every complete feasible advice stream and -robust. Our LAD baseline gives -robustness.
We evaluate the stated advice monitor on 60 synthetic 12-request instances, three capacities, and two feasible advice-corruption mechanisms, giving 9,180 exact-rational runs. Exact offline optima and an independent schedule evaluator support the cost comparisons. Optimal advice attains the optimum on these tests, while conservative switching can make poor advice substantially more expensive than the no-advice baseline. We retain all outcomes and provide the full data and code
in the ancillary material; § 5 and Appendix § 16 describe the protocol and its limitations.
At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of on competitive ratios uniform in capacity. Appendix § 8 gives the fixed-location algorithm and both lower-bound arguments.
Our techniques. Our algorithms address two difficulties: assigning requests to future batches and switching between schedules that have served different requests.
A constant-competitive algorithm. We use Next Fit along paths of nested time intervals. A path-load test accounts for group sizes and interval lengths, ensuring capacity and paying for new batches when admission fails. Next Fit prevents descendants from repeatedly charging the same ancestor. § 3.2 develops the rule and its additive charges through a worked example.
Online advice. Switching schedules requires clearing requests that the new schedule may already have served. We separate the service and waiting costs of this clearance. Baseline budgets control service costs; successive decreases in the remaining advice cost pay waiting charges across switches without repeatedly charging an entire advice batch.
Related work
Aggregation with additive waiting and maximum delay. TCP acknowledgment, JRP, control-message aggregation, and MLA have been studied with additive waiting costs and deadlines [12, 18, 10, 5, 6, 3, 4, 9, 2, 28, 22]. Our direct predecessor is the work of Lu et al. [26] on uncapacitated aggregation with per-batch maximum delay. They show that an offline optimum serves consecutive arrival blocks. This yields a polynomial-time offline dynamic program, which also sets the deadlines of their online algorithm. With capacity, such a block may not fit in one service, and splitting it can charge the same waiting period to several batches.
Lu et al. [24] extend the maximum-delay framework to monotone subadditive service costs. With exact batch optimization, they obtain optimal competitive ratios of 2 deterministically and 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 [30] capacitated max-batching model. 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 § 10. This argument does not extend to maximum delay, since each resulting batch pays its own maximum waiting time.
Dynamic bin packing and busy-time scheduling. MinUsageTime dynamic bin packing and busy-time scheduling group items or jobs under capacity constraints and charge the total time for which bins or machines are used [20, 17, 21, 35, 32, 13, 34, 29, 31]. There is a temporal resemblance to our objective: the maximum waiting time of a batch is the length of the union of its requests’ waiting intervals. In LAD, however, these intervals all end at a common service time chosen by the algorithm. Capacity bounds the total number of requests in the batch. In dynamic bin packing, departures free capacity that later arrivals can reuse. Thus the shared busy-time interpretation does not by itself transfer algorithms or lower bounds to LAD, which also charges a distance-dependent service cost.
Learning-augmented LAD. Lu et al. [25] study uncapacitated LAD with additive waiting costs, including deterministic and randomized learning-augmented algorithms using online suggestions of service lengths. We follow their consistency benchmark of any feasible advised schedule. With capacity, our advice also specifies which requests a service completes. It is revealed only at the proposed service time. Our analysis must account for requests that remain pending when the algorithm switches schedules, even if the schedule it starts following has already served them. § 4 gives the switching rule and the residual-advice argument that controls these costs.
Organization. § 2 introduces the model. § 3 develops the constant-competitive LAD algorithm, from the failure of independent distance classes to the Next Fit construction, its analysis, and the arbitrary-size extension. § 4 gives the online-advice algorithm and the route to its consistency and robustness bounds. The appendices contain the fixed-location results, the baseline upper bound, capacity transfer, the detailed path-load and advice proofs, and the arbitrary-size extension.
Preliminaries
In LAD, each request 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.5 extends the model to arbitrary indivisible request sizes.
An O(1)-competitive algorithm for LAD
Capacity makes the uncapacitated maximum-delay algorithm unusable in two different ways. A pending block may contain more than requests, and splitting it can charge the same waiting period to several batches. Serving each radius class separately avoids this split, but loses the waiting-cost sharing between classes. We first isolate that loss and then give the constant-competitive algorithm.
Why separate radius classes lose a logarithmic factor
Round each positive radius upward to a power of two. At every rounded radius , independently serve the oldest requests when are pending, and otherwise serve all pending requests when the oldest reaches age .
Proposition 3.1. For , this independent-class algorithm is -competitive.
Appendix § 9 gives the proof. The following instance shows that the loss is intrinsic to separating the classes.
Let and . For , release one request at radius at every time , where . There are requests in total. The class algorithm serves each request alone and pays per class, hence altogether. Offline serves all requests in one batch at the last arrival and pays . The competitive ratio is therefore even though the entire input fits in one batch. The lost factor comes from repeatedly paying waiting cost that one shared batch pays once.
Next Fit along nested time intervals
We now let radius classes share future batches. For the moment suppose that radii are powers of two. For each radius and each multiple of , collect the requests that arrived in . At time , serve full groups of immediately and retain the remaining requests as one cohort. Give this cohort the home interval . These homes are nested or disjoint.
A selected home is a root and represents one future batch, served at its right endpoint. A cohort may join the nearest selected root containing its home. Suppose that the candidate root has width , while the cohort has requests and home width . The cohort contributes the constant load
on its home. The first factor records capacity use; the second records how long the candidate owner keeps that capacity. The cohort joins the root only if the total load on its home remains at most one. Otherwise it opens a new root. Later descendants test this new root rather than returning to older ancestors. This is Next Fit along each path of nested homes.
The load test already implies capacity feasibility. The integral of the load assigned to a root of width is per request and is at most . Hence at most requests join the root. Every assigned request has radius at most and waits at most , so the resulting batch costs at most .
A worked example. Let . Two requests of radius arrive at time ; two requests of radius arrive at time ; and at time one request of radius and one of radius arrive. Figure 1 follows the six requests.

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 , the radius- cohort opens the root with load . The radius- cohort with home contributes and joins it. At time , the radius- request reveals home and would contribute , taking the load there to . It therefore opens a new root and is served at time , for cost . At time , the final radius- request reveals home . This home is disjoint from , so its test sees load and it joins the first root. That root serves five requests at time , for cost . The algorithm pays , while one offline batch at time costs .
The rejection at leaves a capacity slot unused, but it also gives a lower-bound certificate. Either the incoming cohort contributes a constant load, or the old load is already large throughout its home. In the second case, the area under that old load pays for the new root. Next Fit is important here: the first rejected descendant becomes the owner for later descendants, so smaller roots do not repeatedly charge the same area.
The algorithm and its guarantee
For arbitrary radii, fix a scale and round upward to the smallest . Define
Thus the cohort with home is completely known at time from requests arriving in . Homes with the same left endpoint are processed from larger to smaller. Full groups are served first; a nonempty remainder becomes one cohort.
If cohort has requests and home of width , and is its nearest selected strict ancestor of width , then admitting would give load
The cohort joins if ; otherwise it becomes a root. Every root serves its assigned cohorts at the right endpoint of its home. Algorithm 1 gives the event-driven rule.
Algorithm 1 Path-load aggregation for LAD
Require: Capacity ; one fixed scale ; deterministic tie orders
Use for the deterministic version; for Corollary 3.3, draw uniformly from once and set .
Initially no requests, cohorts, or selected roots are stored.
On arrival of request at :
;
Store in the cohort with home .
At a virtual arrival time :
for nonempty homes in decreasing do
the requests stored for this home
while do
Serve the first requests of at and remove them from .
if then
Create cohort with , , and .
the selected strict ancestor of of minimum width, if any
if exists then
if exists and then
Assign the entire cohort to .
else
Select as a root, set , and assign to itself.
Schedule its service at .
At the service time of a root :
Serve all requests assigned to in one batch; retire .
Theorem 3.2. There is a deterministic online algorithm for LAD with capacity whose competitive ratio is at most . For radii on one fixed scaled dyadic grid, the ratio is at most
The guarantees also hold for adaptively generated inputs.
Why the analysis is additive
The proof compares request charges inside each batch of an arbitrary offline partition. This is necessary because one offline batch may take parts of several online cohorts. Fix such a batch and write
Serving at its last arrival costs . Let be the fraction of its capacity occupied by requests that remain after local preprocessing.
There are three charges. Full preprocessed batches charge at most inside . For each residual request assigned to a root of width , give the request weight . This weight records the area reserved for that request. For a threshold , call a new root heavy when its own prospective load in its parent is at least ; distribute the heavy root’s width over the requests that created it, giving weights .
The proof uses the following three bounds:
and the total width of light roots is at most . The first two inequalities use maximal represented homes. They are disjoint and lie in an interval of length . Capacity pays for the remaining requests. The light-root bound integrates the old load over the disjoint rejected homes of each parent. Appendix § 11 proves these statements and also shows why trying older roots before the nearest root can lose a logarithmic factor in this certificate.
Each root batch costs at most three times its width. Combining the three charges and maximizing over gives
At , these coefficients are and . On a scaled dyadic grid, ; for arbitrary radii, . This proves Theorem 3.2. The threshold appears only in the proof, not in the algorithm.
Corollary 3.3. Against an oblivious adversary, LAD with capacity admits a randomized online algorithm with expected competitive ratio
Draw uniformly from and use the common scale . For a fixed radius , its rounded value satisfies . Since the rounding map is monotone, the largest rounded radius in is . Taking expectations in (5) proves the corollary. The input must be fixed independently of ; the exact continuous scale is interpreted in the ideal random-real model.
Arbitrary request sizes
The same algorithm handles indivisible sizes . In each cohort, serve requests larger than separately, apply Next Fit to the others, and keep the final nonempty bin as the residual cohort. Replace by its total size and by in the path load. The integral of that load bounds the assigned size by .
Corollary 3.4. The deterministic and randomized guarantees of Theorem 3.2 and Corollary 3.3 hold for arbitrary indivisible request sizes, including zero sizes. Neither algorithm needs a minimum-size assumption or an optimum bin-packing oracle.
Appendix § 14 gives the weighted preprocessing and the complete proof.
Learning-augmented capacitated LAD
We next ask whether a good proposed schedule can improve the online cost without sacrificing the worst-case guarantee. Advice is revealed only when it proposes a service: at time , an event specifies a capacity-feasible set of already arrived requests to serve. The algorithm sees neither future events nor the total advice cost. Consistency is measured against every complete feasible advice stream, including one that is not optimal.
The difficulty is not merely deciding when to stop trusting advice. Two schedules that have processed the same arrivals may have served different requests. After a switch, the new schedule may refer to requests that are no longer pending, while requests already served by the new schedule may still be pending physically. Clearing the physical queue restores a common state, but one advice batch may then be split across several clearances. Its maximum waiting cost cannot be charged in full at every switch.
Theorem 4.1. For LAD with capacity , let be a deterministic -competitive online algorithm. For every , there is a deterministic online algorithm such that
The consistency bound holds for every complete capacity-feasible advice stream revealed at its service times. The robustness bound is independent of advice quality and also holds for incomplete advice. The algorithm has polynomial overhead for rational input and whenever is polynomially simulable.
Using Theorem 3.2 for gives -robustness.
Scores and switches
The algorithm continuously simulates the advice schedule and the robust baseline . For a pending set at time , let
where each minimum ranges over partitions into groups of at most requests. Sorting the requests by decreasing radius computes ; sorting them by decreasing age computes . The two partitions may differ, but is a lower bound on the cost of clearing .
For a virtual schedule , let be the cost it has paid and its pending set. Its score is
The score is nondecreasing. If is complete and feasible, then : restrict its future services to its current pending requests. Thus the score is both observable online and bounded by the final cost of a valid source.
Set
The monitor uses dyadic budget levels . At level , advice is eligible when , while the baseline is eligible when . The monitor prefers advice whenever it is eligible. If neither source is eligible, it doubles the level. A change of level without a change of source requires no physical action.
When the active source changes, the algorithm first serves every physically pending request. It then follows services of the new source, restricted to requests that remain physically pending. The cleanup on a return to advice also removes requests that virtual advice served while the baseline was active. Consequently, during an block the physical pending set is a subset of . Appendix § 12 gives the complete event order and pseudocode, including simultaneous arrivals, services, and score timers.
Two simple packing procedures provide the required cleanups. An ordinary cleanup costs at most
For any , a biased cleanup costs at most
The monitor uses the biased cleanup when leaving advice, because consistency has only an margin for waiting cost. It uses the ordinary cleanup when returning to advice. The smaller baseline budget pays for the latter and for the service-cost part of leaving advice.
The residual-advice charge
The central accounting step pays the waiting part of every exit from advice without reusing an advice batch. Fix the original advice batches , and let be the set of requests already served physically. Define the remaining advice cost
This is an analysis potential, not future information available to the algorithm. It starts at and never increases.
A physical service that follows advice decreases by its own cost. Suppose instead that the monitor leaves advice at time and clears a pending set . Every request in is still pending in virtual advice. For each affected advice batch, deleting these requests either removes the batch or advances its oldest surviving arrival to at least . The decrease in its waiting cost is therefore at least the maximum age of the deleted requests from that batch. Since the affected advice batches form a feasible partition of , the total decrease is at least . Hence
where is the cost of physical services that follow advice. Successive switches use successive decreases of ; none charges the original maximum waiting cost twice.
Completing the two bounds
The remaining accounting is geometric. An advice block ending at level pays at most for its followed services and waiting cleanup. A baseline block ending at level pays at most , including its exit cleanup. Each level is the last level of at most one block of each source. If advice is complete, the levels used by baseline blocks and by exits from advice each sum to at most . Together with (13), this gives
For robustness, no bound on the advice cost is used. The largest opened level is at most , and all opened levels sum to less than twice that value. Applying the same block bounds gives
Since , Theorem 4.1 follows. Appendices § 12 and § 13 prove the cleanup, block, and completion statements used here.
The dependence on cannot be removed. Already at one location, a deterministic -consistent algorithm that is -robust on inputs of at most requests must satisfy
Thus any robustness bound uniform in is at least ; the proof appears in Appendix § 13.
Controlled Advice Experiments
We evaluate the stated monitor, including its unmodified constants, on 60 synthetic request instances of size 12: 20 fixed seeds for each of bursty, spread-out, and mixed-scale arrivals. Testing capacities gives 180 cases with exact offline optima. An exhaustive subset-partition DP computes ; the experiment driver reveals advice services individually at their proposed times. The monitor never receives future advice. We use and compare with path-load without advice and with directly following feasible advice.
Protocol and measurement. The three families vary arrival density and the range of request radii; the same request instance is reused across capacities and monitor settings. Every input and outcome is retained. We report the mean of per-instance ratios, not a ratio of pooled costs. Pointwise 95% intervals use 2000 stratified bootstrap replicates over instance seeds, keeping the capacity variants of each instance together. The benchmark oracle partitions subsets into batches of size at most , each served at its last arrival. Its exponential running time confines this exact-OPT study to small inputs. It is independent of the polynomially simulable online rule. All monitor events and costs use rational arithmetic; a separate evaluator checks the physical schedule for complete, capacity-feasible service and recomputes its total cost.
Systematic lateness. Starting from an optimal schedule with batches, shift each proposed service later by . This preserves its partition and makes exactly, allowing direct comparison across capacities. The experiment varies this ratio from 1 to 10001 to expose both the consistency and fallback regimes. The large errors are deliberate stress tests, rather than an assumed prediction-error distribution.
Figure 2 shows mean finite-input cost divided by exact OPT. With optimal advice, every monitor attains ratio 1.00, versus 2.69 for the baseline on average. With systematic lateness, the monitor initially follows advice: all three settings still have ratio 11 when ADV / OPT = 11. Its proven thresholds are conservative. At quality 1001, the mean ratios are 602.72, 223.62, and 75.42 for , respectively, all above the baseline. Smaller protects consistency but postpones fallback. The observed leveling at the largest tested errors is consistent with fallback; the universal bound comes from the proof.
Figure 2. Controlled advice evaluation, using all generated instances. (a) Shift every optimal advice batch by , where is its number of batches, so exactly. (b) Capacity dependence at advice quality 1001. Shading and error bars are pointwise 95% stratified cluster-bootstrap intervals, resampling request-instance seeds within each family and retaining their capacity variants together. Colors identify the same in both panels; the dashed black curve is the path-load baseline.
At the same level , baseline eligibility uses only , , and in these settings; advice uses .
Feasible partition errors and scope. A separate treatment selects optimal batches, shuffles their requests, and repartitions them into capacity-feasible groups, serving each at its last arrival. The realized advice-to-OPT ratios range from 1 to below 4.053. In this range all three monitors have the same physical cost as following advice and make no nonempty switch. This complements the lateness test, but the two treatments do not isolate error structure at matched quality. The tests establish neither average-case superiority over path-load nor scalability on large demand traces. They isolate the behavior of the stated, untuned monitor and identify switching thresholds as a concrete target for improvement.
Appendix § 16 gives the full protocol, family-wise curves, a separate capacity-feasible repartitioning experiment, and all 9180 exact-rational monitor runs. These controlled schedules isolate advice quality; they are not predictions produced by a trained model.
Conclusion and future directions
The constant competitive ratio for capacitated LAD leaves several questions open. What are the optimal deterministic and randomized competitive ratios? Our bounds show that capacity does not force a logarithmic loss, but a gap remains even against the lower bounds from a single location. For online advice, our robustness is , while the deterministic lower bound is uniformly in capacity. Closing this gap is another natural question. The controlled advice experiments also expose a practical limitation of the current constants: middle-error inputs can trigger fallback only after paying much more than the baseline. Improving these thresholds while retaining consistency and robustness is a further direction.
Extending the constant guarantee beyond a line is a further direction. Does capacitated JRP with maximum delay admit a constant competitive ratio or a constant approximation ratio? For rooted-tree MLA, how should the competitive ratio depend on capacity and tree depth? The LAD admission rule uses nested intervals to control both capacity and the cost of opening batches. For branching service costs, requests can share some edges while paying separately for others; an extension must account for both forms of cost sharing.
Capacity constraints also merit study in online service and facility-location problems with waiting costs. How does maximum delay interact with capacity that can be reused through an opened facility, rather than assigned to a single instantaneous service?
Declaration of AI Use
Generative AI tools assisted mathematical exploration, proof development, drafting, literature searches, experimental-code preparation, and LaTeX preparation. The authors are responsible for the results, references, code, and final text.
Capacitated TCP acknowledgment with maximum delay
The TCP algorithm below handles the single-location special case of LAD and each distance class in § 3.1. We prove its optimal deterministic competitive ratio of two, followed by the randomized lower bound stated in the introduction.
A 2-competitive algorithm
For a fixed setup cost , 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 2 records this rule. All services occur at the current event time. A stale timer is replaced whenever its buffer changes.
Algorithm 2 The fixed-location full-or-age rule
function FullOrAge()
Maintain an arrival-ordered queue .
On an arrival block, append its requests to in a fixed tie order.
while do
Serve and remove the first requests.
After arrival actions, if and its oldest age is at least , serve all of and empty it.
Otherwise schedule the nonempty queue’s timer at its oldest arrival plus .
A timer serves the entire nonempty queue. If , 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 § 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.
Detailed analysis of the path-load algorithm
This appendix proves the feasibility and charging statements summarized in § 3. It also explains why the nearest-owner rule is needed by the batchwise certificate.
Strict time rounding and local preprocessing
We write 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 1).
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 § 14. The bound assigns preprocessing cost to individual requests. Later we combine these charges with those of residual requests inside each offline batch, using their shared capacity constraint.
The path-load rule
We write 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 1). A root serves all its assigned requests at time . This service time and all earlier assignments remain fixed.
All information used in (D.2) is available online. An ancestor home is revealed before its descendants, with the specified order handling equal left endpoints. A newly revealed descendant starts strictly before its ancestor’s right endpoint, and hence its selected ancestor has not served. Homes starting at an endpoint are outside the interval ending there; simultaneous arrivals and due services cause no ambiguity.
All tie choices are fixed in advance. Empty cohorts create no events.
Lemma D.1. Every root batch is capacity feasible, and its actual cost is at most . 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. □
The complete event-driven rule is Algorithm 1 in the main text.
Two additive certificates
A rejected cohort opens another batch, whose cost must be compared with the offline solution. We use two request charges. The first records the load already assigned to an owner; it will pay for rejections caused by that load. The second pays for a new root when its own cohort contributes a large load. Each charge is bounded inside an arbitrary offline batch. Summing over the offline partition bounds the total charge, even when the batches’ arrival spans overlap.
We fix any feasible offline partition into batches. Each batch 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 D.2. 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 D.3. 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 D.4. 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 2.
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 D.2.
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 3 illustrates the disjoint areas used in Lemma D.4. The accounting follows ownership: nested selected roots do not repeatedly use one ancestor’s requests.
Figure 3. Why the light-root charge does not repeat down the hierarchy (schematic density). A light child’s own term is below , 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 D.1–D.4, 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 (D.1), 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 (D.3) 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
Proof of Corollary 3.3. 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 (D.3) 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.
The full online-advice monitor
This appendix gives the complete monitor, its residual-advice proof, and the algebra behind the two guarantees stated in Theorem 4.1.
Packing costs and virtual schedules
The algorithm serves radius-zero requests immediately for free and removes them from advice. We therefore assume positive radii below. An input containing only radius-zero requests costs nothing.
Separate packing costs. For a pending set 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 E.1. 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 E.1 appear in Appendix § 13.
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 E.2. 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 (E.3) for and (E.2) 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: ; continuously simulated advice and baseline
1: ; 2: ; 3: For maintain its own pending set and paid cost . 4: ; maintain physical pending separately. 5: Serve radius-zero arrivals immediately and remove their identifiers from advice. 6: At the first positive-radius arrival block , admit to all three queues; set and active source before service events. 7: function 8: 9: while and do 10: 11: if then 12: 13: else 14: 15: if then 16: if then 17: 18: else 19: ▷ No cleanup on a same-source level change 20: Define and .
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.
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.
Figure 4 summarizes the two kinds of cleanup and the order of operations at a triggering event.

Figure 4. 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 E.3. 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.
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 E.4. 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 (E.7) by its actual service cost.
For an change at time , we write . By Lemma E.3, 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 E.3.
Figure 5 shows the waiting credit at one exit and how credits telescope.

Figure 5. 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 § 13. 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 E.5. For an block,
For a block, the followed services together with its exit cleanup cost at most .
Lemma E.6. 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 E.4 pays for followed advice services and the waiting part of leaving . The service part is bounded by (E.9), and Lemma E.5 pays for complete blocks. Using the two geometric sums in Lemma E.6 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 (E.10) over blocks, bound their additional service-cost cleanup terms by (E.9), 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 (7). Completion and the polynomial-time implementation are verified in Appendix § 13. □
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 E.7. 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 § 13; the optimal dependence on is open.
Supporting proofs for the online-advice algorithm
Section 4 gives the algorithm, the residual-advice argument, and the competitive bounds. This appendix proves the packing and budget lemmas used there, verifies completion and implementation, and proves the robustness lower bound.
Packing procedures and scores
Proof of Lemma E.1. For (E.2), the procedure sorts requests by 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 (E.3), 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 (E.3). ∎
Algorithm 5 implements the two clearance procedures.
Algorithm 5 Clearing pending requests at an advice switch
function SortPack()
Sort by nonincreasing , breaking ties by request identity.
return consecutive groups of requests, with a shorter last group if needed
function PackValue()
return
function Clear()
for
if then
else
Serve every nonempty at ; remove its members from physical pending.
Proof of Lemma E.2. 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 (E.5), 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 E.5. 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 (E.10). For , apply (E.2) 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 E.6. 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 (E.11) 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 (E.12). The final assertion is a geometric sum.
Completion and implementation
We finish the proof of Theorem 4.1 by verifying completion and online computation. On a finite input, is finite, and hence (E.12) 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 E.7. We normalize the setup cost to one. The adversary releases the first request at time zero and advises its immediate singleton service. After the algorithm serves request , 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 (E.13); 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.5.
Proof of Corollary 3.4. Under the preprocessing of § 3.5, 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.5, 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 D.2 and D.3 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 D.4 charges each request at most . Combining these bounds with preprocessing gives exactly (D.3). The deterministic and random-scale conclusions follow with the same constants. The operations use cohort packing, tree ancestry, and arithmetic on revealed data; no optimum bin packing is required.
Algorithm 6 replaces only the cohort preprocessing and the load units in Algorithm 1. It retains the final nonempty bin even when its load is exactly .
Algorithm 6 Weighted cohort preprocessing for the path-load algorithm
Require: Home cohort $Q$ of width $y$, revealed at $b$; capacity $K$
1: Serve every $r \in Q$ with $s_r > K/2$ as a singleton at $b$.
2: $T \leftarrow \varnothing$
3: for remaining requests $r$ in a fixed order do
4: if $\sum_{q \in T} s_q + s_r > K$ then
5: Serve $T$ at $b$; $T \leftarrow \varnothing$.
6: $T \leftarrow T \cup \{r\}$
7: if $T \ne \varnothing$ then
8: Pass $T$ as one residual cohort to Algorithm 1.
9: Use $M_v = \sum_{r \in T} s_r$ and replace $g$ by $K$ in every path-load term.
10: Leave assignments, ancestor selection, and root service times unchanged.
11: Retain a nonempty zero-load residual cohort; nonemptiness is not a load test.
Top- delay at one location
The fixed-location case also admits a constant guarantee when a batch pays the sum of its largest waiting times. Retain the cardinality capacity and let denote the number of charged waits. A batch of at most requests costs its fixed setup plus , the sum of its largest waiting times. The algorithm and comparator use the same . Requests arriving together retain their multiplicities.
The rule. Keep requests in arrival order. At each arrival epoch, serve full batches of oldest pending requests until fewer than remain. Serve the remaining buffer when its top- waiting sum first reaches . Full-batch actions precede a simultaneous timer. New arrivals have zero age, so they do not jump the clock; full-batch actions clear the entire old buffer before any newly created residual buffer can age.
Theorem H.1 (A uniform fixed-location bound). The full-or-top- rule is strictly 3-competitive for every , independently of both parameters. For , no deterministic algorithm has competitive ratio strictly below two.
Proof. Fix a feasible comparator and let be its total setup cost. For each of its eventual batches , let count the requests assigned to that have arrived and are still unserved. Then
This follows by integrating the waits of the oldest requests in each batch.
The algorithm’s positive-length buffer episodes have disjoint interiors. Each ends by clearing the old buffer in a full batch or a timer batch. All their delays are at most , and timer batches have delay exactly . For comparison bookkeeping, reveal arrivals, perform all online full-batch actions, then the comparator’s actions, and finally any online timer. Mark an episode when the comparator first serves a request currently in its buffer. At a comparator action there is only one current buffer, and no further buffer can start after the timer at that timestamp. Thus marked episodes have distinct comparator batch witnesses, and their total delay is at most . Throughout an episode ending unmarked, all buffer requests are still pending offline. Partition them by their eventual comparator batches. The inequality
bounds the buffer’s rate by the integrand in (H.1). Disjoint episode interiors therefore give . This also handles an episode cleared by an arrival action whose requests are served offline at the same endpoint: its open interval is still chargeable.
Let and count full and timer batches. Since full batches contain distinct requests, . Also . Consequently,
A nonempty residual buffer has clock rate at least one and reaches its timer in finite time. There are at most services, so completion requires no end notification. If , immediate service is optimal.
For , the two offset adjacent-pair schedules in the proof of Theorem A.3 remain feasible. Each offline pair is served at its later arrival and has waits ; each algorithm batch in that adversarial construction is a singleton. Their costs are unchanged for every , so the deterministic lower bound of two follows.
The old proof of a factor two cannot simply replace “short span” by “small top- cost.” For , , and , arrivals have three maximal consecutive prefixes with endpoint top-2 cost at most four: , , and . Yet the two groups and both satisfy this condition. Thus the corresponding greedy minimum-number lemma is false. The theorem above concerns the fixed-location case; it does not change the general LAD or advice guarantees elsewhere in the paper.
Advice Experiment Protocol and Additional Results
Instances, capacities, and the exact benchmark
We use 20 fixed seeds per family, indexed , and 12 requests per instance. All arrivals and radii are quarter-integers. Before evaluation we subtract the earliest arrival from every timestamp and sort requests by arrival, retaining distinct identifiers at ties. The generator seed is , where is the instance index and is the family index. The same requests are evaluated at all three capacities.
| Family | Unshifted arrival distribution | Radius distribution |
| Bursty | Uniform center in , plus 0 or 1/4 | Uniform in |
| Spread-out | Uniform quarter-grid in | Uniform in |
| Mixed-scale | Uniform quarter-grid in | Uniform in |
Table 1.
Arrivals and radii are independently generated within these specified families. These distributions are controlled synthetic tests, not calibrated demand models.
For a nonempty request subset with , its canonical batch cost is
It is attained by serving at the last arrival of ; later service only increases cost. Thus exact offline optimization on these finite instances is set partitioning. With , we compute
The restriction to the least identifier removes permutation duplicates. Costs are computed as integers in quarter units, and the minimizing batches are reconstructed. This exponential oracle is used only for the 12-request benchmark; no polynomial-time exact algorithm for general capacitated LAD is claimed. Independent restricted-growth partition enumeration agrees on 72 six-request/capacity tests. The single-location gap formula is checked on two additional instances.
Algorithms and information available
The robust source is exactly path-load with fixed scale and the deterministic tie order in Algorithm 1. The monitor uses and without tuning. We also record the independent-class full-or-age baseline from § 3.1.
The experiment driver constructs complete advice and baseline event lists. Decisions use only current virtual queues, paid costs, the event currently revealed, and the endogenous score timer. Future advice is accessed only by the driver and invariant checker. Arrivals precede virtual services at ties; advice services precede baseline services; waiting timers are processed after the timestamp’s arrivals and services. Physical requests are served once, in batches of size at most . Cost includes all services after the final arrival, without sending an end-of-input notification to the algorithm.
The exact-rational simulator is derived from the existing event audit. For every run, it checks complete service, capacity, source-score monotonicity, the residual-advice potential charge, and the stated consistency/robustness inequalities. A separate cost evaluator recomputes costs from the recorded physical schedule. An additional 111 prefix checks test that the path-load schedule before a cutoff does not change when future input is deleted. The six-request example in Figure 1 has checked algorithm cost 30. These finite checks support implementation fidelity; the universal guarantees are proved in the preceding appendices.
Two advice corruption mechanisms
Systematic lateness. Take an exact optimal schedule with batches and delay every service by . Its request partition is retained, so it remains complete and capacity feasible, and its cost is exactly . We use
The large values intentionally expose the fallback regime of the conservative monitor. They are not a claim about typical prediction errors. In total this part has runs.
Feasible repartitioning. For , select optimal batches using a seeded random order. Shuffle their request identifiers and form groups of at most , serving each at its last arrival. Other batches are retained. This changes the partition while maintaining feasibility and completion. The partition shuffle seed is , held fixed as changes. Advice quality need not be monotone in . There are runs. The realized advice-to-OPT ratio lies between 1 and 4.053; every monitor has the same physical cost as following advice and makes no nonempty switch in this regime. Figure 7 therefore shows their common cost, separately by capacity.
Figure 7. Capacity-feasible partition corruption. All three monitor settings coincide with follow-advice on these tests. Bands are pointwise 95% stratified bootstrap intervals over request-instance seeds.
Figure 6. All three input families separately, using the same instances and parameters as the pooled main-text plot. Dotted gray is follow-advice; dashed black is the path-load baseline. Each curve averages over 20 seeds and three capacities. No family or seed is omitted.
Aggregation, uncertainty, and reproducibility
The plotted estimator is the mean finite-input ratio , not a long-run stochastic ratio. In the pooled curves, we resample the 20 seeds within each family, retaining all three capacity variants of a sampled instance together. We use 2000 stratified paired cluster-bootstrap replicates with seed 20261113 and report pointwise percentile intervals. They are not simultaneous confidence bands or evidence for untested input families. Capacity-specific intervals use the corresponding fixed-capacity data.
Every generated input and all 9180 outcomes are included in the accompanying anc/experiments/results/advice_experiments.json. The self-contained monitor_core.py, run_advice_experiments.py, and plot_advice.py reproduce the data and plots. Exact simulation uses the Python standard library; plotting additionally uses NumPy and Matplotlib. The unfavorable middle-corruption and poor-advice results are retained. They identify conservative switching constants as a limitation of the present implementation, alongside the benefit of optimal advice.
Additional information-flow audit. The script anc/experiments/reviewer_audit.py changes both future arrivals and future advice while preserving each observed prefix. Across 540 paired runs, all physical actions and budget decisions through the cutoff agree; these prefixes include 77 nonempty switches. It also rechecks all 9180 exact cost records, the 180 optimal advice schedules, and the independent small-instance oracle tests. This finite differential check supports implementation fidelity and does not replace the online-information argument in the proof. Lateness and repartitioning have different realized error ranges, so their comparison does not isolate error structure at a matched advice-to-OPT ratio. The original outcomes and algorithm constants are unchanged.
References
- [1]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, Łukasz Jeż, Dorian Nognenġ, 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, Łukasz 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.DOI
- [22]Young-San Lin and Alex Turoczy. Improved and parameterized algorithms for online multi-level aggregation. In Proc. SWAT, pages 31:1–31:17, 2026.arxiv.org/abs/2511.23211
- [23]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online bin packing with per-bin maximum delay. arXiv:2609.29589, 2026.arxiv.org/abs/2609.29589
- [24]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online covering with maximum delay under subadditive service costs. arXiv:2609.32675, 2026.arxiv.org/abs/2609.32675
- [25]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Learning-augmented and randomized algorithms for line aggregation with delays. arXiv:2607.27807, 2026.arxiv.org/abs/2607.27807
- [26]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Online multi-level aggregation with per-batch maximum delay. arXiv:2608.06796, 2026.arxiv.org/abs/2608.06796
- [27]Mathieu Mari, Michał Pawłowski, Runtian Ren, and Piotr Sankowski. Online multi-level aggregation with delays and stochastic arrivals. In Proc. ISAAC, pages 49:1–49:20, 2024.arxiv.org/abs/2404.09711
- [28]Jeremy McMahan. A D-competitive algorithm for the multilevel aggregation problem with deadlines. arXiv:2108.04422, 2021.arxiv.org/abs/2108.04422
- [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.DOI
- [33]Steven S. Seiden. A guessing game and randomized online algorithms. In Proc. STOC, pages 592–601, 2000.DOI
- [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.DOI
- [36]Jingyang Zhao and Mingyu Xiao. Improved approximation algorithms for capacitated vehicle routing with fixed capacity. In Proc. MFCS, pages 931–939, 2025.



