Capacitated Line Aggregation with Maximum Delay

arXiv:2610.26497 · cs.DS · Submitted 2026-10-19 · Read on arXiv

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

Where the paper says it

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 algorithm provides a deterministic online algorithm with a competitive ratio of 36 + 12√3, and its analysis extends to the learning-augmented model 8. p. 7
Where the paper says it

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.

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

Where the paper says it

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.

The algorithm uses a Next Fit idea along paths of nested time intervals to assign a new group when a path-load test permits, or opens a new batch otherwise 6. p. 0
Where the paper says it

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.

This path load controls both capacity and the cost of opening new batches 6. p. 0
Where the paper says it

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√3)/ ln 2 against an oblivious adversary 8. p. 0
Where the paper says it

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.

Both guarantees extend to arbitrary indivisible request sizes 8. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

A failed admission test opens a new batch and provides a charge for its cost 6. p. 5
Where the paper says it

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.

The path load accounts for both group size and waiting time scale 6. p. 5
Where the paper says it

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.

The first factor is the fraction of capacity used; the second compares the owner’s time scale with the cohort’s own time scale 8. p. 5
Where the paper says it

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

Where the paper says it

Its batch is served at its right endpoint. Larger intervals are processed first when their left endpoints coincide.

The total cost is bounded by the sum over offline batches of 3 (1 + 1/(1 - θ))DB + C(θ)YB < 56. p. 9
Where the paper says it

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.

785 14. The choice of threshold θ = 1/(1 + √3) minimizes C(θ) and gives A(θ) = 6 + √3, C(θ) = C∗ = 18 + 6√3 27. p. 7
Where the paper says it

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.

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

Where the paper says it

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.

The learning-augmented model allows for (1+ε)-consistency against every complete feasible advice schedule and O(ε−2)-robustness 16. p. 0
Where the paper says it

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 robustness bound is O(ε−2) for the LAD baseline 16. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

The switching rule controls the pending requests and charges that remain additive across switches 18. p. 3
Where the paper says it

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.

The score HX is nondecreasing, and if X is complete and feasible, then HX(t) ≤ CX for all t 20. p. 0
Where the paper says it

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.

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

Where the paper says it

Consequently, ALG OPT ≥ 2mR 3R − 2 ≥ 2m 3 = Ω(log k). Thus the logarithmic bound is tight for this algorithm.

For the single-location special case, the optimal deterministic competitive ratio is two 21. p. 1
Where the paper says it

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 randomized lower bound for the fixed-location special case is at least e/(e − 1) 23. p. 1
Where the paper says it

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.

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

Where the paper says it

Leaving a capacity slot unused preserves a load budget for subsequent groups. What pays for opening another batch?

Capacity constraints also merit study in online service and facility-location problems with waiting costs 30. p. 3
Where the paper says it

Learning-augmented LAD. [25] study uncapacitated LAD with additive waiting costs, including deterministic and randomized learning-augmented algorithms using online suggestions of service lengths.

The paper also discusses extending the model to rooted-tree MLA for branching service costs 24. p. 1
Where the paper says it

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.

The analysis of robustness shows that the deterministic lower bound is Ω(ε−1) uniformly in capacity 21. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

A full-batch trigger has priority over a simultaneous timer, and every resulting batch costs at most 2w 23. p. 5
Where the paper says it

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 greedy partition into maximal arrival-ordered short prefixes minimizes the number of short batches, even when nonconsecutive groups are allowed 24. p. 5
Where the paper says it

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.

p. 5
Where the paper says it

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.

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

Where the paper says it

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.

The resulting ratio approaches two as N grows 23. p. 2
Where the paper says it

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.

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

Where the paper says it

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.

p. 1
Where the paper says it

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 dependence on ε is necessary even on inputs that fit in one batch at one location 25. p. 3
Where the paper says it

At one location, LAD is capacitated TCP acknowledgment. Inputs are finite, but their number of requests and end time are not announced.

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

Where the paper says it

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.

The deterministic and randomized guarantees hold for arbitrary indivisible sizes, including zero sizes 29. p. 0
Where the paper says it

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.

The algorithm requires no optimum bin packing 30. p. 2
Where the paper says it

Capacitated batching and capacity transfer. [23] study bin packing with per-bin maximum delay and arbitrary positive item sizes.

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

Where the paper says it

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.

p. 5
Where the paper says it

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 proof of Corollary 3. p. 9
Where the paper says it

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 .

8 shows that the deterministic and randomized conclusions follow with the same constants 30. p. 3
Where the paper says it

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

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

Where the paper says it

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.

The final cost is at most 3 (1 + 1/(1 - θ))DB + C(θ)YB 27. p. 6
Where the paper says it

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.

Proof of Theorem 4. p. 4

Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

p. 4
Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

1

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

Where the paper says it

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.

This yields the bound ALG ≤ (1+ε)CA 26. p. 4
Where the paper says it

Consequently, ALG OPT ≥ 2mR 3R − 2 ≥ 2m 3 = Ω(log k). Thus the logarithmic bound is tight for this algorithm.

The final assertion is a geometric sum 27. p. 6
Where the paper says it

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.

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

Where the paper says it

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.

Letting ∆ ↓ 0 proves (4. p. 8
Where the paper says it

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.

15); k = 1 is immediate 23. p. 3
Where the paper says it

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.

Letting k → ∞ gives the stated lower bounds on robustness uniform in capacity 25. p. 1
Where the paper says it

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 optimal dependence on ε is open 25. p. 5
Where the paper says it

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.

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

Where the paper says it

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.

The deterministic and random-scale conclusions follow with the same constants 30. p. 3
Where the paper says it

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

The operations use cohort packing, tree ancestry, and arithmetic on revealed data; no optimum bin packing is required 30. p. 2
Where the paper says it

Capacitated batching and capacity transfer. [23] study bin packing with per-bin maximum delay and arbitrary positive item sizes.

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

Where the paper says it

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.

p. 4
Where the paper says it

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 resulting cost is at most (1 + η)D(L, t) + (1 + 1/η)S(P - L), which is bounded by (4. p. 7
Where the paper says it

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.

p. 7
Where the paper says it

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.

p. 7
Where the paper says it

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.

5) 27. The proof of Lemma 4. p. 4
Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

3 shows that arrivals and waiting only increase packing values 27. p. 3
Where the paper says it

Capacity bounds the total number of requests in the batch. In dynamic bin packing, departures free capacity that later arrivals can reuse.

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

Where the paper says it

An algorithm receives advice only when a proposed service is due. We combine this advice with any deterministic R-competitive baseline.

p. 1
Where the paper says it

An algorithm receives advice only when a proposed service is due. We combine this advice with any deterministic R-competitive baseline.

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. p. 2
Where the paper says it

Switching schedules requires clearing requests that the new schedule may already have served. We separate the service and waiting costs of this clearance.

p. 2
Where the paper says it

Switching schedules requires clearing requests that the new schedule may already have served. We separate the service and waiting costs of this clearance.

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

Where the paper says it

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.

The greedy partition into maximal arrival-ordered short prefixes minimizes the number of short batches, even when nonconsecutive groups are allowed 24.

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

Where the paper says it

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.

The discrete event that exhausts the active cap triggers selection using tentative post-event scores, before the event is committed 18. p. 8
Where the paper says it

Every residual cohort has one owner with a finite prescribed service time, proving the last claim. Algorithm 2 summarizes the complete event-driven rule.

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

Where the paper says it

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.

This ensures that indivisible requests remain intact 30.

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

Where the paper says it

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.

At a triggering arrival or active service, tentative post-event scores are used to select the level and source 18. p. 1
Where the paper says it

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.

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

Where the paper says it

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

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

Where the paper says it

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.

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

Where the paper says it

Summing over the offline partition bounds the total charge, even when the batches’ arrival spans overlap. We fix any feasible offline partition into batches.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

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

Where the paper says it

In the second, charge it to twice the old load integrated over its home. A root’s actual batch cost is at most three times its length, so it suffices to pay for these lengths.

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

Where the paper says it

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

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

Where the paper says it

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.

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

Where the paper says it

The homes that charge a fixed parent root are disjoint. A request assigned to that parent therefore pays at most twice its reserved area in total, even if many smaller roots are subsequently opened.

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

Where the paper says it

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.

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

Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

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

Where the paper says it

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.

**Proof of Theorem A. p. 4

Where the paper says it

For k ≥ 2, the independent-class algorithm is O(log k)-competitive. The proof of the upper bound appears in Appendix B.

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

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

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

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

Related papers