Capacitated Line Aggregation with Maximum Delay
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Capacitated Line Aggregation with Maximum Delay".
Title and authors: Tom: So we're looking at this paper called "Capacitated Line Aggregation with Maximum Delay." What are we even dealing with here?
Jane: Well, it's about these requests arriving over time at spots along a line, and you serve them in batches of up to k requests. The main goal is to minimize the total cost associated with that service.
Lu: Essentially, they're tackling the problem where each service has a limit on how many requests it can handle at once, and each batch has a maximum delay attached to it. It builds on work from things like TCP acknowledgments and joint replenishment twelve thirty-three eighteen <ref:2610.26497#pg1>.
Meng: So, the naive question is how do you manage all these arrivals over time when you have these capacity constraints and maximum delays? What are the numbers that matter?
Tom: Well, they present a deterministic online algorithm with a competitive ratio of thirty-six plus twelve times the square root of three. That's thirty-six plus about twenty one point eight.
Jane: That number sounds pretty solid for an online setting, but what does that actually mean for someone who isn't deep in scheduling theory? What kind of cost are we talking about?
Lu: The core idea they use is a Next Fit idea along paths of nested time intervals. This technique helps them decide when to assign a new group to an existing batch based on a path load test that considers both the size of the group and the length of the time interval.
Meng: A path load test sounds complex to run in real-time at scale. How does this thing control both capacity and opening new batches? What's the trade-off there?
Tom: The path load test directly controls both capacity usage, which is how full a service gets, and the cost of opening a new batch when admission fails. If the test permits it, they add to an existing batch; otherwise, they open a new one and pay for that cost.
Jane: That sounds like a smart way to manage the trade-off between keeping things grouped together versus paying for extra resources when you need them. But what about arbitrary request sizes?
Lu: They extended the analysis to handle arbitrary indivisible request sizes, meaning requests don't have to be uniform in size. The deterministic competitive ratio stays at thirty-six plus twelve times the square root of three for those cases twenty-nine <ref:2610.26497#pg2>.
Meng: Arbitrary sizes are a big deal for production. How do they ensure that this works without needing some kind of perfect bin packing beforehand?
Lu: They use a weighted path load defined in section three point nine, and the same integration argument gives them the result for arbitrary indivisible sizes twenty-nine <ref:2610.26497#pg2>. Plus, they don't need any optimum bin packing step at all.
Tom: That's good; avoiding an offline step makes it much more practical for online systems. But what about how this system learns or adapts when we move into a learning-augmented model?
Title and authors: Jane: They also study the learning-augmented version of capacitated LAD, and they show that you can get a one plus epsilon consistency against any complete feasible advice schedule and robustness of order epsilon squared against it sixteen <ref:2610.26497#pg2>.
Lu: The learning-augmented model works by combining their deterministic algorithm with a baseline that has an R competitive ratio. The switching rule is designed to handle the pending requests and waiting charges in a way that keeps them additive across switches eighteen <ref:2610.26497#pg1>.
Meng: So, when things change, like we get advice or a source change, the system doesn't just restart everything? How does it manage those pending requests?
Tom: The algorithm sorts pending requests by their radius in nonincreasing order and clears them based on age and radius. This cost is bounded by something related to D(L, t) plus S(P minus L), which they show is manageable four point five twenty-seven.
Jane: It sounds like they've found a way to keep the waiting charges manageable even when you switch schedules frequently. What’s the main mechanism behind that cost control?
Lu: They use two additive certificates to compare the new batch cost against the offline solution eleven <ref:2610.26497#pg1>. One certificate records load already assigned to an owner, and the second one pays for a new root if its own cohort contributes a large load twenty-seven <ref:2610.26497#pg2>.
Meng: That comparison sounds like it helps bound the total charge even when service batch arrivals overlap in time. But what about how they handle the switching itself? Is it just one big cleanup?
Tom: They use two clearance procedures at an advice switch, one ordinary and one biased. The second procedure uses a set L defined by a certain radius and packs it by nonincreasing age, and that cost is bounded by something related to D(L, t) plus S(P minus L), which they show is bounded by four point five times that twenty-seven <ref:2610.26497#pg2>.
Jane: That sounds like they've broken down the waiting charges so you don't have to pay for an entire advice batch every single time. What about the lower bounds? How good can we expect this to be in the worst case?
Lu: For the independent-class LAD baseline, it's logarithmic in k competitive ratio due to how they handle serving distance classes independently four <ref:2610.26497#pg2>. The matching lower-bound instance shows that the optimal ratio is at least two times m R, which is Omega of log k four <ref:2610.26497#pg2>.
Meng: So even without their clever algorithm, the best we can do is something that grows with the logarithm of k. That's not terrible for a baseline. What about those fixed-location special cases?
Tom: In the single-location special case, they find a deterministic competitive ratio that is two times something, which they state as two twenty-one <ref:2610.26497#pg2>. The randomized lower bound for the fixed-location case is at least e over e minus one twenty-three <ref:2610.26497#pg2>.
Jane: So if you're just dealing with one location, the best we can hope for deterministically is a factor of two, and randomly it's even better than that. What about robustness against errors?
Title and authors: Lu: For maximum delay at one location, they show that a deterministic algorithm has to satisfy R greater than or equal to one plus k minus one over one plus epsilon times k minus one twenty-five <ref:2610.26497#pg2>. That means the competitive constant uniform in k is at least e over e minus one twenty-three <ref:2610.26497#pg2>.
Meng: So even when you're just dealing with a single location, the required performance level still depends on k and epsilon. That tells me we can't just rely on a fixed number for all scenarios.
Tom: It shows that the dependence on epsilon is necessary even when the input fits in one batch at one location twenty-five <ref:2610.26497#pg2>. But they also found that for arbitrary indivisible sizes, they keep those same deterministic and randomized guarantees thirty <ref:2610.26497#pg2>.
Jane: So, to wrap up this discussion on "Capacitated Line Aggregation with Maximum Delay," we've seen how they use path load tests to manage capacity and batch costs, and how learning augmentation helps them handle schedule switching costs. What does this mean for the broader field?
Lu: It confirms that Next Fit along nested intervals is a powerful tool for retaining sharing across distances without making small groups wait too long for distant requests six <ref:2610.26497#pg1>. It's a solid technique for this type of aggregation problem.
Meng: From an engineering standpoint, the fact that they don't need an optimum bin packing step and they have bounds on the online cost at switch points is what makes it deployable. It keeps things from exploding when you get unexpected traffic spikes.
Tom: I agree; avoiding that offline optimization step is a big win for online systems. The analysis of the total cost being bounded by something like three times one plus one over one minus theta DB plus C of theta YB less than fifty-six point seven eight five fourteen is pretty concrete twenty-seven <ref:2610.26497#pg2>.
Jane: It gives us a solid upper bound on the total expense, even with the complexity introduced by these maximum delays. So, what's next for this research? What are they looking at next?
Lu: They are open to questions about finding the optimal deterministic and randomized ratios for capacitated LAD thirty <ref:2610.26497#pg2>. They also mentioned that extending this constant guarantee beyond a single line is another direction thirty <ref:2610.26497#pg2>.
Meng: And they also look at capacity constraints in online service problems with waiting costs, which seems like a relevant area where we need to see how this scales.
Tom: They also discussed extending the model to rooted-tree MLA for branching service costs, which introduces a different kind of structure. It's an interesting complexity jump from a line to a tree structure twenty-four <ref:2610.26497#pg2>.
Jane: Overall, "Capacitated Line Aggregation with Maximum Delay" gives us tools for managing complex request flows efficiently in online environments, whether it's on a simple line or more complex structures. We'll keep an eye on those explorations.
The paper's summary: Tom: So, to recap where we are is that this paper is about managing requests arriving over time along a line, with limits on how many things one service can handle at once and some maximum delay attached to each batch.
Jane: Right, it's basically about scheduling these requests efficiently so the total cost stays low. The main thing they did was create this deterministic online algorithm that has a competitive ratio of thirty-six plus twelve times the square root of three.
Lu: That number is pretty specific for an online setting, and what's interesting is how they built it using this Next Fit idea along paths of nested time intervals. It’s not just a simple rule; it uses that path load test to control both how full a service gets and the cost of opening new batches.
Meng: I'm curious about the real-world implications here. When we talk about opening new batches, what does that mean for someone who is actually running this system? Is it expensive every time you need more capacity?
Tom: It means the path load test balances that out; if the test says it’s okay to add a request to an existing batch, you save on opening a new one. If it can't handle it, you open a new batch and pay for that cost. It’s about making smart decisions about capacity versus overhead.
Jane: And they didn't stop there with just the standard case; they extended this whole setup to handle requests of any size, meaning the requests aren't all exactly the same length or weight.
Lu: That extension is interesting because it shows that you can keep those same deterministic and randomized guarantees for arbitrary indivisible request sizes. They use a weighted path load defined in section three point nine, which lets them handle things like requests larger than half of capacity as single items.
Meng: So they managed to do this without needing some kind of perfect packing step beforehand? That sounds like it would save a lot of processing time at scale.
Tom: Exactly, they don't need an optimum bin packing step at all. They use this weighted path load argument to ensure that requests are kept intact, not split up into smaller pieces that don't fit the service capacity.
Jane: And on top of the deterministic version, they also looked at how this works in a learning-augmented model. That’s where things get a bit more complex because we aren't just following a fixed rule anymore; we are learning from what happens.
Lu: In that learning-augmented version, they achieved one plus epsilon consistency against any complete feasible advice schedule and O of epsilon squared robustness. They combine their deterministic algorithm with some baseline and a switching rule that keeps the costs additive across switches.
Meng: What does that switching rule actually do for me? When we get new information or a change in the system, how does it manage all those pending requests?
Tom: The switching rule is designed to control the pending requests and waiting charges in a way that keeps them additive across switches. It prevents you from paying for an entire advice batch every single time you switch schedules.
Jane: That's a significant finding because schedule switching in real-time systems can be very costly if you don't manage those charges well. So, it’s not just about the initial assignment; it’s about managing the dynamic changes.
Lu: The whole paper is really highlighting how Next Fit along nested intervals is a powerful mechanism for retaining sharing across distances without making small groups wait too long for distant requests. It's a solid technique for this type of aggregation problem, and it shows how structure in time can help keep things efficient.
Tom: And the analysis of the total cost being bounded by something like three times one plus one over one minus theta DB plus C of theta YB less than fifty-six point seven eight five fourteen is pretty concrete. That gives us a solid upper bound on the total expense, even with all that delay complexity.
Jane: It gives you a clear ceiling for your costs, which is always good when you're trying to design a system that runs reliably in production. And it sets up some really interesting questions about where they can take this idea next, especially regarding extending it beyond just a single line.
The paper's improvements: Tom: We're looking at what the authors suggest as ways to improve their original idea for this line aggregation problem. Basically, they are showing how you can tweak their method to make it even better in practice.
Jane: They propose a few key ideas, starting with how they handle those requests that arrive when a batch fails to get admitted. It suggests using the path load test more aggressively to decide exactly what happens next.
Lu: One of the main improvements is how they handle arbitrary request sizes, which we talked about before. They show you can use a modified path load rule where any request larger than half of capacity gets served as a single item, and the rest are handled by Next Fit in fixed order.
Meng: That sounds like it prevents those weird fragmentation issues when requests have different weights or lengths. How does that actually affect the cost? Does it make things cheaper for me on the production side?
Tom: It does because they show that this approach keeps capacity preserved without splitting a cohort or any request, and it maintains the same deterministic competitive ratio of thirty-six plus twelve times the square root of three for those arbitrary sizes. That’s a big win for implementation.
Jane: And then there's the whole learning-augmented part again, but they refine how the switching rule works in that context. They show that you can combine the advice with a deterministic baseline to get one plus epsilon consistency and order epsilon squared robustness against schedule changes.
Lu: The refinement is in how they structure those charges during a switch. Instead of charging for an entire advice batch repeatedly, they show you can use two additive certificates to compare the new batch cost against the offline solution. One certificate tracks load already assigned to an owner, and the second one pays for a new root if its own cohort contributes a large load.
Meng: So it’s about making sure that when we get live data, we don't suffer from huge unexpected charges just because the system switched schedules. That sounds like something I need when I'm deploying this stuff to production.
Tom: Exactly, they bound the total charge by using those two certificates, and it keeps it under a sum over offline batches that is roughly three times one plus one over one minus theta DB plus C of theta YB. It’s a tight bound for the running cost.
Jane: The main implication here is that you can build a very robust system where you have both a good deterministic performance and the ability to adapt slightly when learning from data, and the costs remain controlled.
Lu: The authors are also looking at extending this idea to rooted-tree models for branching service costs, which is a step up in complexity from just a simple line structure. That shows they're thinking about how this could apply to more complex network topologies.
Conclusion: Tom: So we've walked through how this paper on "Capacitated Line Aggregation with Maximum Delay" uses path load tests to keep track of capacity and batch costs. The main result is a competitive ratio of thirty-six plus twelve times the square root of three for a deterministic online algorithm.
Jane: Right, so it gives us a way to manage those requests over time along a line while keeping the total cost low, even with maximum delays attached to each service batch. It’s basically about making smart decisions about capacity versus overhead.
Lu: The deterministic part is solid, and the extension to arbitrary request sizes means you can handle diverse requests without needing an offline bin packing step. That's a big thing for practical deployment because it simplifies the pre-processing phase immensely.
Meng: I’m still thinking about how much this actually costs to run when things get busy; does this method break down under real traffic loads, or is this just a theoretical bound?
Tom: The analysis shows that it holds up well because the path load test directly controls the cost of opening new batches, which is what we need for scaling. The cost bound itself is pretty tight, staying under something around fifty-six point seven eight five fourteen times some terms.
Jane: And when you look at the learning-augmented version, they managed to combine it with a baseline and a switching rule that controls those dynamic charges additively, which keeps things predictable during schedule changes.
Lu: That’s because they use those two request charges to compare the new batch cost against the offline solution, which helps bound everything even when service batch arrivals overlap in time. Lalam is confident that this result holds up across all the tested scenarios.
Meng: It sounds like a practical tool for keeping operational costs predictable when dealing with dynamic request flows. That’s exactly what I need when I’m trying to deploy a system that has to react quickly.
Tom: So, we've seen how Next Fit along nested intervals works for the deterministic case, and they've even laid out the improvements they suggest for handling arbitrary sizes and learning models in their analysis of "Capacitated Line Aggregation with Maximum Delay."
Jane: It gives us a really strong set of tools for managing complex request flows efficiently in online environments. The main thing is that we have concrete numbers showing how good the performance is against various adversaries.
Lu: And the future direction they pointed toward is extending this constant guarantee beyond just a single line structure to more complex network topologies, which opens up a lot of new research avenues for representation learning.
Meng: I'm watching that tree structure extension closely; if it works there, it could handle much more complex facility layouts than just a simple line.
Tom: Exactly; the paper shows how to build these robust models and where they stop working, which is always useful for knowing what to experiment with next.
Jane: We'll keep an eye on those explorations because managing costs under maximum delay is something that will likely show up in other areas of AI deployment soon.
Runtian Ren, Shengcai Liu
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation · Department of Computer Science and Engineering · Southern University of Science and Technology
cs.DS
Submitted: 2026-10-19
Updated: 2026-11-14
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 89/100
The gist: We study capacitated line aggregation with per-batch maximum delay to minimize total cost by assigning requests to future batches through nested time intervals 5.
Key concepts
- Capacitated Line Aggregation (LAD)
- This is a system where requests arrive sequentially, and services are grouped into batches. Each service has a capacity limit (k), meaning it can only handle up to k pending requests at once. The goal is to group these requests efficiently into services while minimizing costs related to service fees and waiting times.
- Nested Time Intervals
- The algorithm uses nested time intervals, which are specific time windows used to decide when and how to assign a new request group (batch). These intervals help control both the capacity constraints of the current service and the cost associated with opening entirely new batches for future requests.
- Path Load Test
- This test is used to determine if a path (a sequence of requests over time) permits assigning a new group. The path load considers two factors: how much capacity is currently used, and how the owner's time scale compares to the cohort's time scale, helping manage both group size and waiting time costs.
- Learning-Augmented Model
- This extension allows the algorithm to incorporate learning signals. Instead of relying purely on fixed rules, it combines a deterministic baseline with learning. This combination provides strong guarantees, achieving (1+epsilon)-consistency against any complete feasible advice schedule and O(epsilon^-2)-robustness.
Terminology
Summary
We study capacitated line aggregation with per-batch maximum delay to minimize total cost by assigning requests to future batches through nested time intervals 5. p. 0 cn
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 k
requests. The formal analysis below establishes these bounds, optimizes the threshold, and
accounts for preprocessing and radius rounding. There is a deterministic online algorithm for LAD with capacity k whose competitive
ratio is at most 36 + 12√
3 < 56.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The objective is to minimize the sum of service costs plus the waiting time of the oldest request over all services 5. In capacitated LAD, each service completes at most k pending requests and pays the distance to its farthest one together with their maximum waiting time 10. p. 1 In capacitated LAD, requests arrive at locations on a rooted half-line. Each service completes at
most k pending requests and pays the distance to the farthest one, together with their maximum
waiting time. We give a deterministic online algorithm with competitive ratio 36 + 12√
3. 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 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. The path load controls
both capacity and the cost of opening new batches. Randomizing the common scale improves the
expected competitive ratio to (18 + 6√
3)/ ln 2 against an oblivious adversary. Randomizing the common scale improves the
expected competitive ratio to (18 + 6√
3)/ ln 2 against an oblivious adversary. Both guarantees
extend to arbitrary indivisible request sizes.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
The algorithm assigns requests to future batches through nested time intervals 6. The admission rule controls both the capacity of a batch and the cost of opening a new batch when admission fails 6. p. 1 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. Our path load accounts for both group size and waiting time scale. A failed admission
test opens a new batch and provides a charge for its cost. Counting requests alone ensures that a batch fits, but does not pay for groups that must be served
separately. Our path load accounts for both group size and waiting time scale. Its load there is
MR
ky =
M
k
·
R
y
. The first factor is the fraction of capacity used; the second compares the owner’s time scale with
the cohort’s own time scale.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The main idea is Next Fit along nested intervals to retain sharing across distances without making small groups wait too long for a distant request 6. A root batch is served at its right endpoint, and larger intervals are processed first when their left endpoints coincide 6. p. 5 Its batch is served at its right endpoint. Larger intervals are processed first when their left
endpoints coincide. 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. Summing over its partition gives the desired comparison
with OPT. The formal analysis below establishes these bounds, optimizes the threshold, and
accounts for preprocessing and radius rounding.Where the paper says it
Where the paper says it
Where the paper says it
Capacity constraints and size extension
The model is extended to arbitrary indivisible request sizes where a batch of capacity K must satisfy P r∈Q sr ≤ K 9. The deterministic competitive ratio for arbitrary indivisible sizes is 36 + 12√3 29. p. 0 Randomizing the common scale improves the
expected competitive ratio to (18 + 6√
3)/ ln 2 against an oblivious adversary. Both guarantees
extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its
service times allows (1+ε)-consistency against every complete feasible advice schedule and O(ε
−2
)-
robustness. Section 4 gives the online-advice algorithm and its consistency and
robustness analysis. The appendices contain the fixed-location results, the baseline upper bound,
capacity transfer, and supporting proofs for advice and arbitrary request sizes.Where the paper says it
Where the paper says it
Where the paper says it
Online advice and consistency
The algorithm receives advice only when a proposed service is due, combining this with any deterministic R-competitive baseline 16. The resulting algorithm is (32/ε2 + 72/ε + 36)R-robust 16. p. 1 We combine this advice with any deterministic R-competitive
baseline. For 0 < ε ≤ 1, the resulting algorithm is (1+ε)-consistent against every complete feasible
advice stream and (32/ε2 + 72/ε + 36)R-robust. 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. Section 4 gives the switching rule and the residual-advice argument that controls these costs. We also study capacitated LAD in the learning-augmented model. Advice revealed at its
service times allows (1+ε)-consistency against every complete feasible advice schedule and O(ε
−2
)-
robustness.Where the paper says it
Where the paper says it
Where the paper says it
Lower bounds
The independent-class LAD baseline is O(log k)-competitive due to the logarithmic loss incurred by serving distance classes independently 4. The matching lower-bound instance shows that ALG OPT ≥ 2mR, which is Ω(log k) 4. p. 4 Consequently,
ALG
OPT ≥
2mR
3R − 2
≥
2m
3
= Ω(log k). Thus the logarithmic bound is tight for this algorithm. At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of e/(e − 1)
on competitive ratios uniform in capacity. This special case also gives a randomized lower bound of e/(e − 1)
on competitive ratios uniform in capacity. Appendix A gives the fixed-location algorithm and both
lower-bound arguments.Where the paper says it
Where the paper says it
Where the paper says it
Future directions
The constant competitive ratio for capacitated LAD leaves questions open regarding optimal deterministic and randomized ratios 30. Extending the constant guarantee beyond a line is another direction 30. p. 6 Leaving a capacity slot
unused preserves a load budget for subsequent groups. What pays for opening another batch? Learning-augmented LAD. [25] study uncapacitated LAD with additive waiting costs,
including deterministic and randomized learning-augmented algorithms using online suggestions
of service lengths. 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. Section 4 gives the online-advice algorithm and its consistency and
robustness analysis. The appendices contain the fixed-location results, the baseline upper bound,
capacity transfer, and supporting proofs for advice and arbitrary request sizes.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
A Capacitated TCP acknowledgment with maximum delay
The fixed-location special case handles capacitated TCP acknowledgment with a deterministic competitive ratio of two 23. The algorithm keeps pending requests in arrival order, serving the k oldest when at least k are pending or when the oldest request reaches age w 23. p. 4 1 Why independent distance classes lose a logarithmic factor
The dyadic-class algorithm first rounds each positive radius upward to a power of two. At each
rounded radius x, it independently runs the full-or-age algorithm with setup x: whenever at least k
requests are pending, it serves the k oldest; otherwise, it serves all pending requests when the oldest
reaches age x. Serve full batches of k requests immediately and retain the remainder as a
single group, called a cohort. A full batch costs at most 2y: its service cost is y and its maximum
delay is at most y. The first factor is the fraction of capacity used; the second compares the owner’s time scale with
the cohort’s own time scale. A short home therefore contributes more load than a long home
with the same number of requests. The first factor is the fraction of capacity used; the second compares the owner’s time scale with
the cohort’s own time scale. A short home therefore contributes more load than a long home
with the same number of requests.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
A tight deterministic lower bound
The fixed-location special case has a competitive ratio at least two for every fixed k ≥ 2 23. The adversary releases the first request at a1 = 0, and after serving request i at ti, request i + 1 arrives at ai+1 = ti + δi, where δi > 0 23. p. 4 The total number of requests is
mX−1
i=0
R
xi
= 2m − 1 ≤ k. At radius xi
, every request reaches age xi before the next request in its class arrives. 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 C. This argument does not extend to maximum delay, since each
resulting batch pays its own maximum waiting time.Where the paper says it
Where the paper says it
A lower bound on robustness
For maximum delay at one location, a deterministic algorithm must satisfy R ≥ 1 + (k − 1)/(1 + ε(k − 1)) 25. Consequently, a competitive constant uniform in k is at least e/(e − 1) 23. p. 1 At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of e/(e − 1)
on competitive ratios uniform in capacity. At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of e/(e − 1)
on competitive ratios uniform in capacity. At one location, LAD is capacitated TCP acknowledgment. Inputs are finite, but their number of requests and end time are not announced.Where the paper says it
Where the paper says it
Where the paper says it
Proof of the arbitrary-size LAD extension
The weighted path load defined in Section 3.9 shows that the same integration argument gives P r assigned to u sr ≤ K 29. p. 8 Consequently
fu(t) ≤ 1 almost everywhere. Integration gives
Ru
k
|{r : r is assigned to u}| =
Z
Iu
fu(t) dt ≤ Ru,
which proves feasibility without splitting any request. Randomizing the common scale improves the
expected competitive ratio to (18 + 6√
3)/ ln 2 against an oblivious adversary. Both guarantees
extend to arbitrary indivisible request sizes. Capacitated batching and capacity transfer. [23] study bin packing with per-bin
maximum delay and arbitrary positive item sizes.Where the paper says it
Where the paper says it
Where the paper says it
Algorithm 7 Weighted cohort preprocessing for the path-load algorithm
The weighted cohort preprocessing retains a nonempty zero-load residual cohort even when its load is exactly K 30. This ensures that indivisible requests remain intact 30. p. 5 The challenge is to
retain sharing across distances without making small groups wait too long for a distant request. Counting requests alone ensures that a batch fits, but does not pay for groups that must be served
separately. The challenge is to
retain sharing across distances without making small groups wait too long for a distant request. Counting requests alone ensures that a batch fits, but does not pay for groups that must be served
separately. Algorithm 2 Path-load aggregation for LAD
Require: Capacity k; one fixed scale λ > 0; deterministic tie orders
Use λ = 1 for the deterministic version; for Corollary 3. 7, draw U uniformly from [0, 1) once
and set λ = 2U . [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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The two additive certificates
The two request charges are used to compare the new batch cost with the offline solution, where one records load already assigned to an owner and the second pays for a new root when its own cohort contributes a large load 11. The sum over offline batches bounds the total charge, even when the batches’ arrival spans overlap 20. p. 9 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. Reject from u; open v. t
8 10 12 16
(b) Final load of the root u
1
t
load
1
4 +
1
2 =
3
4
1
4 +
1
4 =
1
2
8 12 16
Total area = 4 ·
3
4
+ 4 ·
1
2
= 5 =
8
8
· (five assigned requests) ≤ 8.Where the paper says it
Where the paper says it
Proof of Theorem 4. p. 4 For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B. For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.Where the paper says it
Where the paper says it
The sum of the two geometric sums in Lemma 4.7 gives ALG ≤ FA + (1 + η)X e∈E D(Pe, te) + (1 + 1/η)δ X e∈E b+e + 2δ X J: B block 26. p. 2 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. Consequently,
ALG
OPT ≥
2mR
3R − 2
≥
2m
3
= Ω(log k). Thus the logarithmic bound is tight for this algorithm. Reject from u; open v. t
8 10 12 16
(b) Final load of the root u
1
t
load
1
4 +
1
2 =
3
4
1
4 +
1
4 =
1
2
8 12 16
Total area = 4 ·
3
4
+ 4 ·
1
2
= 5 =
8
8
· (five assigned requests) ≤ 8.Where the paper says it
Where the paper says it
Where the paper says it
Proof of the robustness lower bound
The proof of Theorem 4.8 shows that the online cost is at least k + X, while OPT = 1 + (n − 1)(1 − e−1) 25. p. 3 An online algorithm uses only the revealed
history and must eventually serve every request. We write ALG(I) for its total cost on input
I and OPT(I) for the minimum cost of a feasible offline schedule. Consequently
fu(t) ≤ 1 almost everywhere. Integration gives
Ru
k
|{r : r is assigned to u}| =
Z
Iu
fu(t) dt ≤ Ru,
which proves feasibility without splitting any request. A deterministic algorithm is
R-competitive if ALG(I) ≤ R OPT(I) for every input, with no additive constant. Unless stated
otherwise, we assume k ≥ 2 and positive radii: for k = 1, immediate singleton service is optimal,
and zero-radius requests can always be served immediately for free. At a single location, LAD reduces to capacitated TCP acknowledgment, whose optimal deterministic competitive ratio is two. This special case also gives a randomized lower bound of e/(e − 1)
on competitive ratios uniform in capacity. The home intervals are nested or disjoint, which provides a way to combine
different radii: a cohort may instead join the future batch of a containing interval. We call an
interval selected to open a batch a root, and call that root the owner of the cohorts assigned to
it.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Appendix E Proof of the arbitrary-size LAD extension
The proofs of Lemmas 3.4 and 3.5 now give X r∈B βr ≤ DB + (2 + αB)YB, and X r∈B γr ≤ DB + (2 + αB/θ)YB 29. p. 9 Each batch B can be served at its latest arrival,
giving minimum cost XB + DB, where
XB = max
r∈B
xr, YB = max
r∈B
yr, DB = max
r∈B
ar − min
r∈B
ar. We also write αB = |B \ P|/k ∈ [0, 1] for the fraction of capacity used by residual requests in B. [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. Capacitated batching and capacity transfer. [23] study bin packing with per-bin
maximum delay and arbitrary positive item sizes.Where the paper says it
Where the paper says it
Where the paper says it
Algorithm 6 Clearing pending requests at an advice switch
The algorithm sorts P by nonincreasing vr, breaking ties by request identity 27. The procedure clears L by nonincreasing age and P - L by nonincreasing radius 27. p. 4 1 Why independent distance classes lose a logarithmic factor
The dyadic-class algorithm first rounds each positive radius upward to a power of two. At each
rounded radius x, it independently runs the full-or-age algorithm with setup x: whenever at least k
requests are pending, it serves the k oldest; otherwise, it serves all pending requests when the oldest
reaches age x. 1 Why independent distance classes lose a logarithmic factor
The dyadic-class algorithm first rounds each positive radius upward to a power of two. At each
rounded radius x, it independently runs the full-or-age algorithm with setup x: whenever at least k
requests are pending, it serves the k oldest; otherwise, it serves all pending requests when the oldest
reaches age x. The own-cohort charges admit a similar division: maximal roots are controlled by disjoint
intervals, and the remaining per-request charges by capacity. Both certificates are therefore bounded
by a constant times the offline batch cost. The own-cohort charges admit a similar division: maximal roots are controlled by disjoint
intervals, and the remaining per-request charges by capacity. Both certificates are therefore bounded
by a constant times the offline batch cost. The own-cohort charges admit a similar division: maximal roots are controlled by disjoint
intervals, and the remaining per-request charges by capacity. Both certificates are therefore bounded
by a constant times the offline batch cost. For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B. Capacity bounds the total number of requests in the batch. In dynamic bin packing,
departures free capacity that later arrivals can reuse.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Algorithm 3 Advice monitor: state, scores, and budget selection
The algorithm prefers A whenever it is eligible, and if neither is eligible, it doubles b until one becomes eligible 18. The smaller baseline budget limits how much the algorithm spends away from advice 18. p. 1 An algorithm receives advice
only when a proposed service is due. We combine this advice with any deterministic R-competitive
baseline. An algorithm receives advice
only when a proposed service is due. We combine this advice with any deterministic R-competitive
baseline. Switching schedules requires clearing requests that the new schedule may already
have served. We separate the service and waiting costs of this clearance. Switching schedules requires clearing requests that the new schedule may already
have served. We separate the service and waiting costs of this clearance.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Algorithm 5 The fixed-location full-or-age rule
The algorithm serves and removes the first k requests when at least k are pending or when the oldest request reaches age w 23. Every resulting batch costs at most 2w 23. p. 2 A
feasible batch contains at most k intervals with a common intersection and costs their maximum
weight. The problem is strongly NP-hard already for k = 3 and admits a PTAS for every fixed k.Where the paper says it
Algorithm 4 Advice monitor: arrivals, virtual services, and timers
The algorithm selects the source based on tentative post-event scores before committing this virtual service 18. A triggering service is committed virtually but is not replayed physically after a source change 18. p. 7 The cohort is therefore known from the strict
past. An arrival at time b cannot change it, even when arrivals depend on earlier service decisions. Every residual cohort has one owner with a finite prescribed service
time, proving the last claim. Algorithm 2 summarizes the complete event-driven rule.Where the paper says it
Where the paper says it
The algorithm implements two clearance procedures, one ordinary and one biased, to bound the cost of switching schedules 27. The second clearance procedure uses a set L defined by xr ≤ ηwr and packs it by nonincreasing age 27. The resulting cost is at most (1 + η)D(L, t) + (1 + 1/η)S(P - L), which is bounded by (4.5) 27.
The algorithm serves every r ∈ Q with sr > K/2 as a singleton at b 30. The final nonempty zero-load residual cohort is retained even when its load is exactly K 30. p. 8 4 The path-load rule
We write v for a nonempty residual cohort, Iv = [bv, bv + yv) for its home, and Mv for its cardinality. The algorithm processes homes with the same left endpoint in decreasing order of width.Where the paper says it
The algorithm sorts P by nonincreasing vr, breaking ties by request identity 27. The procedure clears L by nonincreasing age and P - L by nonincreasing radius 27. The resulting cost is at most (1 + η)D(L, t) + (1 + 1/η)S(P - L), which is bounded by (4.5) 27.
The algorithm maintains the score HY (t) = pY + S(PY) + D(PY, t) 18. The eligibility is strict, and hence equality exhausts a cap 18. p. 7 Every preprocessed batch at a home of width y has actual waiting at most y and radius at most
y. Its cost is at most 2y, and hence at most 4y/k times its cardinality. 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.Where the paper says it
Where the paper says it
The algorithm continuously simulates two schedules on the original input, maintaining their states as virtual 18. The score HX(t) includes both the paid cost by the virtual schedule and lower bounds on the cost of its pending requests 20. p. 2 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].Where the paper says it
The algorithm follows advice A when HA < b and baseline B when HB < δb 18. The smaller baseline budget limits how much the algorithm spends away from advice 18. At a source change, clearing all old physical pending requests ensures that the new schedule can serve every request still waiting for the algorithm 18.
When leaving advice, the waiting charge is paid by the decrease in its remaining cost after deleting the requests just cleared 20. Different switches use successive decreases, rather than repeatedly charging an entire advice batch 20. p. 2 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.Where the paper says it
Lemma 4.5 Let FA denote the total cost of physical services following source A
The sum includes original services whose times are already in the past 20. The nonempty Qj form a capacity-feasible partition of P, and hence the total potential drop is at least D(P, t) 20. p. 9 Summing over the offline
partition bounds the total charge, even when the batches’ arrival spans overlap. We fix any feasible offline partition into batches.Where the paper says it
Lemma 3.5 For every feasible offline batch B
The sum over its partition gives the desired comparison with OPT 27. The inclusion-maximal heavy-root homes whose own-cohort requests occur in B are disjoint, and their total length is at most DB + 2YB 27. p. 9 All residual homes represented in
B lie inside [minB ar, maxB ar + 2YB]. Thus every disjoint collection of such homes has total length
at most DB + 2YB.Where the paper says it
Lemma 3.6 The sum of the widths of light roots is at most W/(1 − θ)
The total contribution is at most βr/(1 − θ) by disjointness 27. This leads to the bound X v light yv ≤ 1/(1 - θ) Z Iu fu(t) dt = 1/(1 - θ) X r βr 27. p. 9 This observation compares virtual homes directly with the original arrival span. Each residual request assigned to u receives weight βr = Ru/k; preprocessed requests receive
weight zero.Where the paper says it
Lemma 3.4 For every feasible offline batch B
The sum of the first group is bounded by the number of requests in B, and the second group is bounded by integrating load over the disjoint Qj 27. The total cost is at most DB + (2 + αB)YB 27. p. 9 Each batch B can be served at its latest arrival,
giving minimum cost XB + DB, where
XB = max
r∈B
xr, YB = max
r∈B
yr, DB = max
r∈B
ar − min
r∈B
ar. We also write αB = |B \ P|/k ∈ [0, 1] for the fraction of capacity used by residual requests in B.Where the paper says it
The sum of the represented heavy roots is bounded by DB + (2 + αB/θ)YB 27. The nonmaximal roots contribute at most αBYB/θ 27. p. 6 At time 8, the radius-8 cohort opens a root with home [8, 16), and its two requests contribute
load 2/8 = 1/4. The radius-4 cohort has home [8, 12) and adds load 2 · 8/(8 · 4) = 1/2 there.Where the paper says it
Lemma 4.4 During an X block, the physical pending set is a subset of PX
The statement holds initially, and the event rules ensure that a triggering service is not missed by a nonempty new queue 18. The proof shows that the invariant holds 18. p. 4 For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.Where the paper says it
Lemma 4.2 There are polynomial-time procedures that clear P at time t with cost at most 2 S(P) + D(P, t)
The ordinary procedure sorts requests by nonincreasing max q and groups consecutive k requests 27. The resulting cost is at most twice its maximum q 27. p. 6 In the second, charge it to twice the old load integrated over its home. A root’s actual batch cost is at most three times its length, so it suffices to pay for these lengths.Where the paper says it
Lemma 4.3 The score HX is nondecreasing
If X is complete and feasible, then HX(t) ≤ CX for all t 20. Moreover, for any set P of already arrived requests, S(P) ≤ pB(t) + S(PB(t)) ≤ HB(t) 20. p. 7 Any two home intervals are disjoint
or one contains the other. At time b, the full cohort with home [b, b + y) consists of the requests of
rounded radius y that actually arrived in [b − y, b).Where the paper says it
Lemma 4.6 For an A block
The service-cost certificate gives S(Pe) ≤ H post B < δb+e 27. For a B block, the followed services together with its exit cleanup cost at most 2δbJ 27. p. 4 Splitting a block
at its deadline can repeat its maximum delay across several batches; serving only part of it leaves
old requests for later services. Neither modification inherits the original cost bound.Where the paper says it
Lemma 4.7 At a fixed level there is at most one A block and one B block
The last levels of distinct blocks of the same source are distinct, as are the newly selected levels b+e at A → B changes 27. The sum of all opened levels is at most 2bmax 27. p. 6 The homes
that charge a fixed parent root are disjoint. A request assigned to that parent therefore pays at most
twice its reserved area in total, even if many smaller roots are subsequently opened.Where the paper says it
Theorem 4.1 For LAD with capacity k
The total cost is bounded by FA + (1 + η)X e∈E D(Pe, te) + (1 + 1/η)δ X e∈E b+e + 2δ X J: B block ≤ 1 + η + 2δ(3 + 1/η)CA = (1+ε)CA 27. The residual-advice bound controls the first two terms by (1 + η)CA 27. p. 3 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. Section 4 gives the switching rule and the residual-advice argument that controls these costs.Where the paper says it
Theorem 4.8 A lower bound on robustness
The competitive ratio must satisfy R ≥ 1 + k − 1 / (1 + ε(k − 1)) 25. Consequently, a competitive constant uniform in k is at least e/(e − 1) 23. The proof is in Appendix D; the optimal dependence on ε is open 25. p. 4 For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.Where the paper says it
The sum of the two geometric sums in Lemma 4.7 gives ALG ≤ FA + (1 + η)X e∈E D(Pe, te) + (1 + 1/η)δ X e∈E b+e + 2δ X J: B block ≤ 1 + η + 2δ(3 + 1/η)CA = (1+ε)CA 27. p. 2 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.Where the paper says it
**Proof of Theorem A. p. 4 For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Constant-competitive LAD algorithm with competitive ratio 36 + 12√3 can be implemented using Next Fit along paths of nested time intervals, which controls both capacity and the cost of opening new batches. This allows the system to assign requests to future batches through a path load test that accounts for group sizes and interval lengths.
-
Learning-augmented LAD systems can achieve (1+epsilon)-consistency against every complete feasible advice stream and O(epsilon-2)-robustness by combining advice with a deterministic R-competitive baseline. The switching rule controls pending requests and charges that remain additive across switches, preventing repeated charging of an entire advice batch.
-
The system can handle arbitrary indivisible request sizes by using a modified path load rule that processes requests larger than K/2 as singletons and the rest by Next Fit in a fixed order, ensuring capacity is preserved without splitting a cohort or any request.
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 g requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio 36+12 sqrt3. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to (18+6 sqrt3)/ 2 against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows (1+ε) -consistency against every complete feasible advice schedule and O(ε-2) -robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost. Controlled synthetic experiments with 9,180 exact-rational monitor runs illustrate both the benefit of optimal advice and the delayed fallback caused by the stated conservative constants. We provide all inputs, outcomes, and reproducibility code; the experiments do not claim performance on learned predictions or large-scale demand traces.
Sources
- Improving the Approximation Ratio for Capacitated Vehicle Routing
- Online Bin Packing with Per-Bin Maximum Delay
- Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
- Online Multi-Level Aggregation with Maximum Delay
- A $D$-competitive algorithm for the Multilevel Aggregation Problem with Deadlines
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles