WorksComputer Science
Stochastic Aggregation with Prescribed Resources and Additive Delay
Abstract
We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served units of time after its arrival incurs delay cost . The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource–scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below . The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.
Introduction
Consider a service system in which each order requires several shared operations. An order may need transmission along a network path, access to a group of machines, or the replenishment of several items. Handling orders immediately repeats these purchases. Waiting allows orders with common requirements to share their cost, but every waiting customer incurs a delay penalty. Even when the required resources are known in advance, deciding which orders to combine remains an online problem.
Rooted multi-level aggregation is a familiar example: a request at a vertex needs every edge on its path to the root. Pair demands on a tree instead need the path between two specified endpoints. More general requirements need not come from paths or have a hierarchy. Three types may require , , and , respectively. Each pair can share one purchase, but no single tree of nested requirements explains all three possibilities. We call the general model aggregation with prescribed resources: a type specifies a fixed resource set, and a batch pays the weight of the union of the sets required by its requests.
Aggregation, replenishment, and related network design problems with delay have received sustained attention in the adversarial model [1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 14]. Their guarantees depend on the service model and on the information available about delay. For example, the recent bound for general delay in rooted aggregation depends on tree depth [1]. Broader service systems also have superconstant lower bounds [14]. Such lower bounds must not be transferred automatically to every tree model or every stochastic arrival assumption.
A provider may know more than the worst-case model allows. Past demand can indicate how often a resource is needed, even though it cannot predict the next order. We isolate this information by assigning every request type an independent Poisson process of known rate. The rates are available before execution; the actual requests are revealed only when they arrive. The comparison remains demanding: the offline optimum knows the entire realized sequence and may choose every batch freely. The question is therefore the following.
Can arrival rates coordinate arbitrary overlapping requirements well enough to obtain a constant guarantee against the clairvoyant optimum?
Mari, Pawłowski, Ren, and Sankowski studied ratios of expectations for stochastic matching with delays and rooted multi-level aggregation [11, 12]. Their aggregation algorithm combines immediate service of light demand with periodic service of heavy demand, and their paper reports a general bound of 210. These works motivate the use of statistical information, but do not coordinate arbitrary resource overlap. Our resource–scale LP handles this overlap and gives a substantially smaller bound for the same uncapacitated rooted problem. The algorithm and proof are independent of the earlier GEN analysis; the present result does not validate or repair that analysis.
Our contributions
We study independent Poisson arrivals of known rates, with each request paying its waiting time. Our guarantees compare the expected cost of an online algorithm with the expected cost of an offline optimum that knows all future arrivals. We consider this ratio over increasingly long horizons, including the full cost of completing every request. Our results address two questions: how well statistical information can coordinate many overlapping resource requirements, and how much it can help even in the simplest one-resource problem.
A constant guarantee beyond tree aggregation. We give a deterministic online algorithm with a ratio below 2.111 for arbitrary prescribed resource sets. Its guarantee is independent of the number of resources, the number of request types, and how their requirements overlap. With a small loss in the constant, we obtain a ratio below 2.113 with polynomial-time preprocessing for rational costs and arrival rates.
This general model includes rooted multi-level aggregation: the resources required by a request are the edges on its path to the root. It also includes aggregation for prescribed pairs of vertices on a tree. Both problems therefore inherit our guarantees. In particular, we improve on the 210 bound reported for stochastic rooted MLA to below 2.111, while extending the result to requirements with no tree structure.
The optimal guarantee for Poisson TCP acknowledgment. When all requests need the same resource, the problem becomes TCP acknowledgment: one acknowledgment can serve several pending requests, but each request pays for its own delay. For arbitrary arrival sequences, the optimal randomized competitive ratio is [9]. We determine the best possible long-run ratio of expectations under Poisson arrivals, obtaining
a worst-case value of about 1.409. A deterministic online policy attains this value, and randomization cannot improve it.
Our characterization is more detailed than a single worst-case bound. For every positive arrival rate and acknowledgment cost, we determine the optimal online cost rate and characterize the offline cost rate. Together they give the optimal ratio for that particular load, which can be substantially smaller than the worst-case value. We also identify the hardest load. Thus the result quantifies exactly the remaining advantage of knowing the future after the arrival rate is already known. Since TCP acknowledgment is a special case of our general model, it also supplies a lower bound for prescribed-resource and tree aggregation.
Table 1 summarizes these two main contributions and their consequences for trees.
| Problem | Upper bound | Lower bound | |
| Finite prep. | Polynomial prep. | ||
| Arbitrary prescribed resources | < 2.111 | < 2.113 | > 1.408 |
| Rooted and pair aggregation on trees | < 2.111 | < 2.113 | > 1.408 |
| Poisson TCP acknowledgment | Optimal ratio: about 1.409 |
Table 1. Worst-case long-run ratios of expectations under known-rate Poisson arrivals. All upper bounds are attained by deterministic online policies. In the first two rows, the polynomial-time preprocessing guarantee assumes rational costs and rates. The TCP result supplies the lower bounds in the first two rows and also characterizes the optimal ratio at every load.
Our techniques
Coordinating purchases through arrival rates. The basic tradeoff is familiar. Serving requests immediately avoids waiting but repeats purchases; collecting requests into batches saves purchase costs but makes them wait. Arrival rates tell us how much sharing we can expect from waiting. With several resources, however, these decisions interact. Two types may benefit from sharing a costly resource even though their other requirements are different. Choosing when to serve each type in isolation can lose this saving, while forcing every type to follow the same schedule can create excessive delay.
Our approach chooses service frequencies jointly and coordinates the resulting service times. Types can be served at different frequencies while still meeting regularly to share purchases. The algorithm buys only the resources needed by requests actually being served. The main challenge is to show that these simple scheduling choices compete with an offline optimum that is free to arrange its batches after seeing the entire input.
Comparing both schedules through the same lower bound. We use a linear program that accounts for resource costs at different time scales. Its lower-bound interpretation splits the original costs among simpler one-resource problems, without counting any purchase or any request’s waiting cost more than once. Every offline schedule must pay at least the sum of these simpler optima. Their Poisson analysis therefore gives a lower bound even for an optimum that knows the future.
The same LP guides the online scheduling choices. This is the essential connection: the lower bound and the algorithm account for the same opportunities to share costs. We can consequently bound both purchase and waiting costs without a loss depending on the size or structure of the resource system. Keeping track of the occasions when there is nothing to serve, and carefully choosing the parameters, gives the stated constant. An efficient preprocessing procedure preserves the guarantee with an arbitrarily small multiplicative loss.

Figure 1. The LP gives both a lower bound on what any offline schedule must pay and coordinated service periods for the online algorithm. The Poisson TCP analysis supplies the one-resource comparisons and an unavoidable lower bound for all causal policies.
Understanding the advantage of knowing the future. The one-resource problem supports the general analysis and is also interesting in its own right. An online policy knows how frequently requests arrive, but it cannot tell whether the next request is about to arrive or is still far away. The offline optimum can use precisely this information when deciding which requests to combine. We determine the best cost achievable without this future information and separately characterize the cost achievable with it. Comparing the two gives the optimal ratio at each load and identifies the worst load. This comparison accounts for all causal policies, including randomized ones, and all offline batching choices. It thus establishes the limit of what arrival-rate information can achieve in this basic problem, in addition to supplying the one-resource estimates used in the general algorithm.
Related work
Aggregation and replenishment. Rooted aggregation includes acknowledgement and joint replenishment as shallow cases. Bienkowski and coauthors obtained an guarantee for general delay on depth- trees [6]. For deadlines, Buchbinder, Feldman, Naor, and Talmon obtained [7], and McMahan obtained [13]. Azar and Touitou improved the general-delay bound to [4]; Ahmadian and coauthors’ recent preprint gives by dual fitting [1]. Azar and Iluz study nonmonotone delay penalties [3], whereas our penalties are known linear functions.
Set-based service and general frameworks. Carrasco, Pruhs, Stein, and Verschae study online set aggregation and give an bound in the number of requests, with a matching randomized lower bound in their model [8]. Azar and Touitou’s frameworks handle several network design problems with deadlines or delay [4, 5]. The latter uses offline optimization primitives, including prize-collecting versions for delay. Set cover with delay and nonclairvoyant frameworks address different service choices or information assumptions [2, 15]. Touitou proves lower bounds for several broader network models [14]. Our union cost is a specified coverage function, and independent known-rate arrivals replace adversarial input.
Statistical information. The stochastic matching and rooted aggregation papers [11, 12] are our closest predecessors in arrival model and performance criterion. We preserve their distinction between a ratio of expectations and an expected samplewise ratio. Information about rates is also distinct from knowing a request’s future delay function, as studied by Le, Umboh, and Xie [10]. Every delay function here is known; its future request arrivals are not.
Organization
Section 2 defines the model and recalls the basic Poisson facts. Section 3 explains the optimal TCP guarantee, and Section 4 develops the general-resource algorithm and the comparisons behind its ratio. Together these sections give the main results and their proof ideas. Sections 5–7 provide the technical tools and complete proofs. Appendix A gives the arithmetic certificates supporting the numerical constants.
Model and basic Poisson facts
Requests, services, and costs
Let be a finite set of resources. Resource has purchase cost , and for . There is a finite set of request types. Each type has a prescribed nonempty resource set and arrival rate . Zero-rate types and unused resources may be discarded; requests with no positive-cost requirements can be served for free. We consider nontrivial instances below.
A request is one occurrence of a type. Write for the type of request , for its arrival time, and for its service time. A service chooses a batch of pending requests, purchases the union of their required resources, and serves them instantaneously. Its purchase cost is
Each resource is paid for once in this batch, regardless of how many requests need it. A later batch must purchase its resources again. Every request receives all its required resources in one service and incurs waiting cost . The objective is the total purchase cost plus the sum of these individual waiting costs.
Services have no duration or capacity restriction, and there is no additional fee per service. An online algorithm may use the known instance and requests observed so far, but not future arrivals. Arrivals at a service time are observed first; simultaneous services are processed in execution order. An offline optimum knows the entire realized input and may choose any feasible batches and service times.
Poisson arrivals and the performance criterion
Each type follows an independent homogeneous Poisson process of its known rate. Equivalently, successive interarrival times for type are independent exponential variables of mean . The rates are known before execution; the realized arrival times are revealed only as requests arrive.
For a horizon , let be the arrivals in . The algorithm receives no signal that the input has ended. It must eventually serve all requests, and includes the entire cost of doing so, even when some services occur after . Let be the minimum cost of completing the same input. For a fixed instance we measure
Thus we compare expected total costs over increasingly long horizons. This is a ratio of expectations, rather than the expectation of a samplewise ratio. Expectations include independent algorithmic randomness when relevant. We write for a finite constant that may depend on the fixed instance but not on .
The basic facts we will use
For a rate- process, an interval of fixed length contains requests in expectation and is empty with probability . Counts in disjoint intervals are independent. Combining independent Poisson streams adds their rates; independently retaining each arrival with probability gives a Poisson stream of rate . These facts let us group request types or extract simpler comparison instances without losing the arrival model.
Conditional on the number of arrivals in a fixed interval, their unordered times are independent uniform points in that interval. In particular, if all arrivals in an interval of length are served at its end, their expected total waiting is
This is the basic calculation behind our periodic schedules. The intervals in these statements are fixed independently of the arrivals. Intervals selected by the offline optimum after seeing requests require a separate argument; we do not assume the same formulas apply to them. More general counting identities and the potential arguments for optimal online policies are introduced only in the technical development, § 5.
One resource: the value of knowing the future
Before coordinating several resources, consider a single resource of cost and requests arriving at rate . Every service buys the resource once and may clear all pending requests. This is Poisson TCP acknowledgment. We use it both to understand the best possible online performance and to measure costs that remain unavoidable when resources overlap.
When is it worth collecting a batch?
If purchases are cheap or requests are rare, immediate service is a natural choice. When purchases are expensive and requests are frequent, waiting for several requests can spread the purchase cost. The product expresses this tradeoff. By measuring time in units of and multiplying all costs by , we obtain a rate-one process with purchase cost . Both cost rates and ratios are preserved. We use these units throughout this section.
Consider serving every th arrival, collecting requests per batch. The mean time from one completed batch to the next is . Each batch costs to purchase. While collecting it, the queue successively has waiting requests, and each next arrival takes one unit of time in expectation. Thus the mean waiting cost per batch is . Dividing the mean total cost by the mean cycle length gives
Choosing the best integer therefore gives the candidate rate
For the best choice is immediate service; for it is two requests per batch; for it is three. At a boundary the two neighboring choices tie. The algorithm uses the known load to choose its batch size before requests arrive.
A count rule alone could leave the last, incomplete batch waiting forever on a finite input. We add deadlines that grow with the batch index. These deadlines always complete the input, while their total expected extra cost is only logarithmic in the horizon. They do not change the long-run rate. The explicit deadlines and their analysis are given in Theorem 6.3.
Why can no online policy do better?
Optimizing over batch sizes does not yet exclude more elaborate policies. An online algorithm could use the entire observed history, randomize its decisions, or serve only part of the queue. To rule out an improvement, we assign the pending queue a nonnegative amount of unpaid cost, represented by a potential.
The potential is chosen so that waiting cost together with the expected increase caused by new arrivals accumulates at rate at least . A service can reduce this potential, but never by more than the purchase cost it pays. Summing these two observations shows that every online policy must pay at least in expectation. Completing the last requests also pays off the final potential. This argument applies to every causal policy, rather than only to count rules.
This is why the simple batching rule is enough: it attains a lower bound that already accounts for every possible online decision. § 6.2 gives the potential explicitly and proves both directions, including finite-input completion.
What can the offline optimum save?
The offline optimum can see whether the next request follows quickly or only after a long silence. It can combine close arrivals and avoid waiting through an unprofitable gap. To measure this advantage, let denote its long-run expected cost per unit time in the same rate-one normalization.
Two elementary observations make this quantity accessible. First, an optimal service can clear all pending requests and occur at the last arrival in its batch. The problem is therefore to partition the ordered arrivals into consecutive batches. Second, a gap of length at least can separate two optimal batches: an extra purchase costs , while splitting saves at least that much waiting. We can therefore divide the arrival sequence at these long gaps and optimize each resulting cluster separately.
Poisson arrivals determine the distribution of cluster sizes and internal gaps. A dynamic program computes the best partition inside each finite cluster. Averaging these costs gives , with a convergent expression and an explicit bound on the error from discarding large clusters. The detailed construction is in § 6.1; rigorous numerical bounds are given in Appendix § 10.
Theorem 3.1 (Optimal Poisson TCP guarantee). For every load , the optimal long-run ratio of expectations among all causal completing policies is . A deterministic policy attains it. Over all positive loads,
The load attains this worst-case value.
At this hardest load, immediate service is already optimal online: its expected cost rate is one. The offline rate is about 0.710. For comparison, at load the optimal ratio is below 4/3, and at it is below 1.25. Thus the theorem describes the best ratio at each load, not only one universal upper bound.
The remaining step in the worst-load proof is to compare different loads. Concavity of reduces this comparison to the loads where the preferred batch size changes. A scaling inequality controls all large such loads, and a few certified comparisons handle the small ones. Corollary 6.4 and Theorem 6.7 give the complete proof.
This result also places a limit on general resource aggregation: its instances include the one-resource example at load one. In the other direction, the offline function will help us build a lower bound for arbitrary overlapping requirements. It is this offline comparison, rather than a separate TCP algorithm on each resource, that we use next.
Many resources: coordinating shared purchases
We now explain how one-resource comparisons lead to a constant guarantee for arbitrary prescribed resource sets. The online algorithm will use a periodic schedule. The central question is how to choose its periods so that shared purchases remain inexpensive, and how to compare this schedule with an offline optimum that can batch freely.
Theorem 4.1 (General resource guarantee). For independent Poisson arrivals of known rates, aggregation with prescribed resources admits a deterministic online algorithm with long-run ratio of expectations below 2.111. For rational costs and rates, a deterministic algorithm with polynomial-time preprocessing achieves a ratio below 2.113. Both guarantees are independent of the number of resources, the number of request types, and their pattern of overlap, and include completion of every finite input.
Two difficulties created by overlap
Suppose one type requires and another requires . Serving them together saves one purchase of . If they use unrelated service times, this saving may disappear. Conversely, making all types wait for the same service time may impose too much delay on frequent types. We therefore need different service frequencies that still allow types to share purchases.
Overlap also makes lower bounds delicate. Solving an independent TCP problem for each resource and adding its cost would charge the waiting of a request once for every resource it requires. The original problem charges that waiting only once. Such a sum need not be a valid lower bound. The algorithm must coordinate purchases, and the analysis must coordinate its charges to waiting cost.
A lower bound that never charges the same cost twice
We split costs into simpler problems, each involving one resource at one time scale. A piece receives part of that resource’s purchase cost and part of the waiting cost of each type that requires it. There are two basic budget rules:
The purchase costs assigned to the pieces of a resource must sum to at most its original purchase cost.
The waiting weights assigned to the pieces of a request must sum to at most its original unit waiting rate.
For example, a request needing may contribute some of its waiting cost to the pieces and the rest to the pieces. It does not contribute its entire waiting cost to both.
Every original schedule induces a feasible schedule for each piece: use the same service times for the relevant requests. The budget rules ensure that the sum of the induced costs never exceeds the original cost. Optimizing each piece separately can only reduce that sum. Consequently, for every realized arrival sequence,
This comparison permits an unrestricted, clairvoyant original optimum. The pieces are used only to measure what it must pay; its actual services need not follow the decomposition.
A resource–scale LP chooses these budgets jointly. It also controls the load in each piece so that the scalar offline analysis applies. Independent thinning of Poisson arrivals converts the different waiting weights into comparable one-resource instances. Averaging the pathwise inequality then gives a lower bound proportional to the LP optimum, denoted by . The full LP and the projection argument appear in § 7.2–§ 7.3.
Turning the same LP into a schedule
The LP dual supplies a service time scale for each request type. We round positive scales to periods of the form
with one common base and all clocks starting at zero. A type assigned period zero is served immediately. A type with a positive period is served at its clock ticks whenever its queue is nonempty. If several types are due together, one service purchases the union of their required resources.
The periods are nested: every tick of a longer period is also a tick of each shorter period. For example, types with periods and can share purchases at every multiple of , while the first type still gets an additional opportunity halfway through. This is how the schedule accommodates different frequencies without losing all coordination. The periods depend only on the known instance, and each actual purchase depends only on the requests already present.
This schedule also accommodates light demand. A zero time scale means immediate service, with no rounding to a positive period. For a type assigned a positive period, the algorithm waits only until its next clock tick, not until another request of that type arrives. A sparse type can therefore share purchases with frequent types without having to wait for its own next arrival. The LP chooses these scales jointly, taking both the arrival rates and the shared resource costs into account.
Waiting cost. A type with rate and period incurs long-run expected waiting cost . This is the fixed-interval calculation from § 2: on average a request waits half a period.
Purchase cost. A clock tick does not always trigger a purchase. For one type of rate and period , the probability that its queue is nonempty is . The purchase cost rate for a resource of cost used by that type alone is therefore
With several types, we similarly count a shared resource only when at least one due queue needs it. Nested periods and independent Poisson streams let us calculate this probability. Retaining these empty-queue savings is important for the constant, particularly for infrequent types.
The dual constraints bound the combined waiting and purchase costs by a constant multiple of the same used in the offline lower bound. Choosing the common base carefully controls the loss in rounding the periods. Averaging over possible choices proves that a good one exists; deterministic preprocessing finds one before the input arrives. No random choices are needed during execution.
Where the constant comes from
The proof has two estimates, both expressed through . With the selected parameters, their coefficients can be rounded outward to give the convenient bounds
Their ratio is below 2.111. The important point is that the size and overlap of the resource system enter through in both inequalities. They cancel in the comparison, instead of appearing as an extra depth, frequency, or resource-count factor. The lower estimate uses the scalar offline cost; it does not multiply the algorithm’s cost by the worst TCP ratio.
The exact coefficients and their parameter choices yield the sharper bound 2.110250205 in Theorem 7.9. For a polynomial implementation, we search a finite rational set of common bases and certify the resulting costs to sufficient precision. This adds an arbitrarily small multiplicative loss. Taking it to be at most 1.001 gives the stated bound below 2.113; the bit-complexity analysis is in Theorem 7.11.
Tree consequences and the remaining gap
For rooted MLA, let each resource be an edge and each request type require its path to the root. The union of these paths is precisely the subtree needed to serve a batch. Both online and offline costs are preserved, so the general theorem immediately improves the 210 bound reported for stochastic MLA, using an independent algorithm and proof.
For prescribed pairs on a tree, a type requires the unique path between its endpoints. A union of paths can have several connected components. Serving those components simultaneously preserves the total edge cost and every request’s additive delay, so the theorem also applies when each service must be connected, provided simultaneous services carry no additional fee.
The TCP example gives a lower bound of about 1.409 for all these models. It does not settle whether arbitrary overlap is harder. The general gap between this lower bound and our algorithm remains open. The two main conclusions are thus different: a constant algorithm for arbitrary resource requirements, and an optimal characterization for the single-resource family.
Guide to the complete proofs. The argument above reduces the general guarantee to three tasks: justify the one-resource projections, bound the cost of the nested schedule by the same LP, and implement its preprocessing efficiently. § 7 proves these in order. § 6 proves the scalar cost formulas and the worst-load comparison. The probability and potential tools needed by these proofs are collected in § 5. Appendix § 10 gives the numerical certificates.
Technical tools for the proofs
Sections 3 and 4 gave the algorithms, guarantees, and their main comparisons. We now develop the complete proofs. This section records the probability identities and queue accounting used below; the next two sections prove the TCP and resource guarantees, respectively.
The first subsection supplies Poisson counting identities, including the insertion formula used to count scalar clusters. The second formalizes the unpaid-cost argument and the completion rule from § 3. Neither queue lemma is needed to understand or execute the prescribed-resource algorithm.
We use for the positive part, for an event indicator, and for the length of a measurable time set. Charging blocks are half-open: an action at the left endpoint belongs to the block and one at its right endpoint belongs to the next. Nonnegative terms permit interchanging sums, integrals, and expectations by Tonelli’s theorem.
Poisson counting identities
For a rate- process, the number of arrivals in an interval has distribution
Counts in disjoint intervals are independent. Conditional on arrivals in a finite interval, their unordered times are independent uniform points in that interval. In particular, for a nonnegative deterministic function ,
Conditioning on the count proves this identity: the conditional expectation is , and . We use it, for example, with equal to the wait until the next deterministic clock tick. Nonnegative integrands also allow us to exchange sums, integrals, and expectations by Tonelli’s theorem.
For independent streams, superposition adds their rates. Conversely, independently assigning an arrival a mark with probability produces independent Poisson streams of rates . The generating function factors into the generating functions of these independent counts. These statements apply to marks chosen independently for each occurrence; arbitrary routing based on the future need not preserve a Poisson law.
The void probability is . It remains valid for a deterministic interval that depends on the instance parameters. We will not apply it to intervals selected by an offline schedule after observing arrivals. Instead, our lower bounds first establish an inequality for every realized schedule and then average a certificate whose counting regions are fixed independently of that schedule.
We also use the following extension of (2), in which the contribution of a distinguished arrival depends on the other arrivals. It will count scalar cluster starts without conditioning on an arrival at one prescribed time.
Lemma 5.1 (Poisson insertion). Fix , and let be a nonnegative measurable quantity defined for a distinguished type- request at time and a finite multiset of other requests. Then
On the right, is an independent Poisson input to which the distinguished request can be added inside the definition of .
Proof. Condition on the number of type- arrivals. Their times are independent uniforms in , and exchangeability makes the sum on the left equal in expectation to times the contribution of one distinguished uniform time, with other type- times. The identity changes the latter points back into an unconditional type- Poisson process. All other types retain their independent laws. Integrating the distinguished uniform time proves (3). No conditioning on an arrival at one prescribed time is needed.
Potential accounting and finite completion
Several proofs use the same queue calculation. Write for the pending-count vector, for its waiting rate, and for the arrival generator. At a service of cost , call its excess. Arrivals are inserted before their triggered services, as in our event convention.
Lemma 5.2. Let be bounded and nonnegative, with . For a causal policy starting empty,
Here includes only costs incurred through . If in every state and every service has nonnegative excess, then every causal completing policy satisfies , including randomized policies and partial services.
Proof. Telescope the potential over arrivals and services. Conditional Poisson compensation replaces the arrival increments by ; independent policy coins are included in the history. Boundedness permits localization for policies of finite expected cost. The lower-bound hypotheses give . After the last arrival, the service inequalities telescope from to , so completion pays this terminal potential. Infinite expected cost already satisfies the lower bound.
The next lemma adds finite deadlines to a count-based policy without changing its asymptotic rate. A busy period starts when its queue becomes nonempty and ends when it becomes empty. Normal services occur only at arrivals.
Lemma 5.3. With as above and unit waiting per request, suppose an untimed policy has at most pending requests between events, in every state it occupies between events, including the empty state, and nonpositive excess at every normal service. Assume clearing any occupied state has excess at most . Conditional on the past at each busy-period start, its untimed duration satisfies for , where and . Suppose the expected number of starts through is at most . Clear period at its normal end or at the earlier deadline
Then every finite input completes without an end signal, and
Proof. The tail bound makes the conditional probability of timeout at most . Their sum is less than one. The accounting identity gives on an infinite continuation. The truncated input has the same prefix. If period is pending at , it clears by its deadline, paying at most afterward. Its index is at most the number of starts through . Jensen’s inequality proves the bound. Every nonempty period has a finite deadline. The tail bound must hold after every history of the timed policy; the start-count bound refers to that policy as well.
Proof of the optimal Poisson TCP guarantee
With one resource, the model is TCP acknowledgment with additive delay: one purchase clears pending requests, and every request pays its own waiting time. We study its known-rate Poisson arrival version. The scalar problem has two roles. Its offline rate gives the resource LP certificate, while the difference between its optimal causal and clairvoyant rates gives a lower bound for every online algorithm. Neither role restricts the offline batch sizes.
For one resource of cost and arrival rate , put . The time change , together with multiplication of cost by , gives rate one and setup cost . Cost per unit time and ratios of expectations are unchanged. The formulas below use these normalized units. In particular, an additive finite-horizon constant must be divided by when returning to the original units.
The exact unrestricted offline rate
For arrivals at times , write . Define and, for ,
An empty sum is zero. Thus , and the cost of serving three arrivals in one batch is . The factor on a gap is the number of requests already waiting while that gap elapses.
Lemma 6.1. The dynamic program gives the unrestricted offline optimum for these arrivals. Moreover, any gap of length at least can be made a boundary between two batches in an optimum.
Proof. At any service, clearing all pending requests costs no more than clearing a subset, and weakly decreases all affected waiting costs. Deleting any resulting empty later services yields a schedule whose batches are consecutive segments of the arrival sequence. Each service can then be moved to the last arrival in its batch, which weakly decreases waiting and preserves the order of services. The final batch after index has exactly the cost displayed in the recurrence, proving completeness of the dynamic program.
Suppose one such batch spans a gap . Split it at that gap and serve its earlier part at the last arrival of that part. The extra purchase costs , whereas at least one earlier request avoids waiting for the entire gap, saving at least . The split therefore cannot increase cost. Repeating the operation establishes the second assertion. □
Put and . Consecutive arrivals separated by gaps smaller than form a cluster; a gap at least separates clusters. For a cluster beginning at a specified arrival, its number of arrivals has distribution
Conditional on , the internal gaps are independent exponential variables conditioned to belong to . Their joint density is on that cube. The exact cost rate is described by the following absolutely convergent series of finite-dimensional integrals.
Theorem 6.2. For every , define
For , the integral denotes the number . Then the unrestricted offline optimum satisfies
In particular its expected long-run cost rate exists and equals . If denotes the series truncated at , then
Also .
Proof. Extend the rate-one Poisson input to the entire real line. The preceding lemma shows that optimal costs add over its clusters. A distinguished arrival begins a cluster precisely when there is no arrival in the preceding interval of length . This event has probability and is independent of the entire future cluster. Thus cluster starts have intensity . If denotes the cost of a whole cluster beginning at a distinguished arrival, the Poisson insertion identity gives
This application can be reduced to the finite-window insertion identity: truncate each cluster after its first arrivals. The resulting quantity depends only on the Poisson configuration in . Let . Deleting requests cannot increase optimum cost, so the truncated costs increase to , and monotone convergence applies. Also and , ensuring integrability.
Conditioning on and its internal gaps gives
All clusters wholly inside contribute exactly the same amount to this stationary reward sum and to . Only clusters crossing or can contribute a difference. Deleting arrivals from a cluster cannot increase its optimal cost, and its full cost is at most times its full size. At any deterministic boundary, the size of a cluster crossing it is bounded by the sum of two geometric() counts: scan backward from the nearest arrival on the left and forward from the nearest arrival on the right, stopping each scan at the first gap at least . Each count has expectation . If the gap straddling the boundary is itself at least , there is no crossing cluster and its contribution is zero. Hence the expected size charged at a boundary is at most . The two boundaries together yield
The same estimate covers the case where one cluster crosses both boundaries, since counting it twice only enlarges the bound.
Finally for every nonempty cluster. In particular the first series term gives . The upper bounds imply and
This proves convergence and the explicit tail error.
The exact causal optimum for every scalar load
Continue in the rate-one normalization, with setup cost .
Define
Choose an integer with
Then and . At a common endpoint either adjacent choice is valid. These facts follow by comparing consecutive terms: their difference is .
Theorem 6.3. For every , every causal completing policy, including randomized policies and policies using partial batches, satisfies
There is a deterministic horizon-unaware policy that completes every finite input and has expected cost rate exactly . For , it satisfies the explicit bound
For , immediate service has expected cost exactly .
Proof. Write and define
The formulas agree at . Since , the potential is nondecreasing and lies in . Moreover,
with equality for . Every service costs and lowers by at most , including a partial clearing. Lemma 5.2 proves the all-causal lower bound.
For the upper bound, serve immediately when . Otherwise clear a batch at its th arrival or at the deadline
after the first arrival of its th batch. Between events the queue has at most requests and drift plus holding exactly . A full batch costs its potential decrease ; a timeout has excess at most . The untimed wait for new arrivals satisfies , hence . At most one batch starts per arrival. Lemma 5.3, with , gives precisely the stated finite-horizon bound. Its excess is , proving attainment of with full completion.
Corollary 6.4. For every , the smallest long-run ratio of expectations among causal completing policies is exactly . One deterministic policy, using the known instance parameters to select the rule above, attains this value on every scalar instance.
Proof. The offline expected cost rate exists and is . Divide the finite-horizon lower bound and the attaining policy’s asymptotic equality by .
Two structural properties of the scalar offline rate
Lemma 6.5. The function is concave on , with . Writing , one has
Proof. For each fixed arrival realization, the offline cost is the infimum over schedules of times the number of services plus their waiting cost. It is therefore concave in . Taking expectations, dividing by the horizon, and passing to the existing cost-rate limit preserves concavity. The free-setup problem has zero cost, and , so the extension at zero is valid.
On , the function is affine with endpoint values . Concavity lower-bounds by the chord between the same endpoints. It follows that is at least the smaller endpoint ratio. For the first interval , use and instead of forming the undefined ratio at zero. Every positive belongs to one of these intervals, proving the supremum identity.
Lemma 6.6. For and ,
Equivalently is nondecreasing.
Proof. Let be a finite realized set of arrival slots, and define
The feasible family is fixed, including when some are zero. Thus is concave as an infimum of affine functions of . Independently retain each slot with probability , writing for its retention indicator and for the retained input. Conditional Jensen gives
The second inequality follows by deleting the zero-weight slots from any schedule completing all slots. Deleting them can only remove feasibility constraints and can never increase the cost of serving the retained requests. In particular we do not move a zero-weight request to a time preceding its arrival, nor claim equality of these two optima.
Now let be a rate- Poisson input in . Its independently retained subset has rate one. Factoring out of the objective gives . Consequently, for every finite horizon including completion,
The normalized scalar cost rate for parameters is . Divide by and pass to the existing limits to obtain the assertion.
The worst scalar load is exactly one
Appendix A certifies the following four strict rational inequalities:
Theorem 6.7. The optimal competitive factor over all positive-rate, positive-setup single-resource instances is exactly
The load attains the worst factor. This is a matching upper and lower characterization for the entire scalar family, including unrestricted clairvoyant batching and all causal randomized policies.
Proof. For the second and third triangular loads,
Furthermore
so . For every , the triangular load satisfies, by Lemma 6.6,
Thus every triangular load after the first has a strictly smaller ratio than . Lemma 6.5 controls every intervening load. At , , so equality holds. Corollary 6.4 supplies both the universal causal lower bound and a completing policy attaining the upper bound.
A numerical lower bound for resource aggregation
The finite-state and conditional-mean certificates in Appendix § 10 give
The lower bound on controls the upper end of the scalar factor; the upper bound on supplies the competitive lower bound. The directions are different and both are needed.
Theorem 6.8 (Competitive lower bound). Every causal algorithm for prescribed-resource aggregation, including randomized algorithms, has worst-instance long-run ratio at least . The same lower bound holds for rooted and prescribed-pair aggregation on trees.
Proof. Take one resource of cost one with a rate-one stream. Every causal completing policy costs at least in expectation by Theorem 6.3, while the offline cost rate is . A single unit edge realizes the instance for rooted and pair aggregation. These embeddings preserve all waiting, purchases, and completion costs.
Thus the optimal uniform resource factor obeys
The exact scalar theorem supplies a matching result only within the single-resource family. Resource overlap may still affect the optimal uniform factor.
Proof of the prescribed-resource guarantee
Each type requires a fixed resource set, and these sets may overlap arbitrarily. A finite LP chooses one time scale per type. After one common phase is selected, the online rule is simply to clear the due nonempty queues and buy their resource union. We prove a ratio below 2.110250205 against the unrestricted offline optimum.
The problem and its tree interpretations
Notation. We use the model of § 2: resource has purchase cost , and type requires and arrives at rate . Remove unused and zero-cost resources, zero-rate types, and types whose remaining requirements are empty; the latter are served immediately for free. If nothing remains the problem is trivial. Otherwise costs and rates are positive and all required sets are nonempty. Each occurrence receives its entire required set in one service, which pays the weight of the union; purchases are repeated in later services. In a tree, is the unique path between the two endpoints of type . Buying the union of these paths gives a forest. Each component may be purchased as a separate connected service at the same time, preserving both total edge cost and each request’s additive delay. Thus the theorem also applies when each individual action must buy a connected subtree, provided simultaneous actions are permitted without additional fees. The line case is the union-of-intervals specialization.
For rooted aggregation, take one type at each positive-rate client vertex and set to its path to the prescribed root. The union of the paths of a nonempty batch is a connected rooted subtree, and trimming any rooted service to this union cannot increase its cost. Thus the resource formulation has exactly the same optimum. A fixed root activation can be represented by one additional resource required by every type. Zero-cost resources may be contracted or removed; requests whose remaining required set is empty are served for free.
The one-resource tradeoff was developed in § 3. With several resources, independent clocks can repeatedly purchase a shared resource that one offline batch buys only once. We therefore allocate purchase and waiting budgets jointly before choosing the service periods.
A lower-bound LP with no repeated charging
Let be a finite set of positive time scales and fix . For each resource–scale pair use a purchase budget , and for each incidence use a charge . The program has objective
and nonnegative variables satisfying
The first and last inequalities allocate the original waiting and purchase budgets. The other two control the size and mean load of the weighted scalar problem at a resource–scale pair. The zero solution is feasible, and all variables are bounded, so an optimum exists. We will prove the paired estimates
Here will be the finite grid ratio, and includes the final clearings. We first establish the lower certificate and then derive the clocks from the dual.
The scalar projection certificate
For a rate-one Poisson process, let be the expected unrestricted offline batching cost on , with purchase cost and unit waiting cost. Define
The exact convergent series and existence of this limit are proved in § 6.1. In particular .
Lemma 7.1. For every , . The ratio is nonincreasing in . For a rate- Poisson process with unit purchase cost and unit waiting cost, its expected offline cost on is at least $C(u)H.
Proof. Every finite single-resource input has an optimum that completes at its last arrival, as proved with the batching dynamic program below. Concatenating optimal schedules on two adjacent intervals is feasible. Independent stationary Poisson increments therefore give . For any positive integer , . Divide by and use the defining limit to obtain the first claim.
For each fixed finite input, its optimum divided by equals
This quantity is nonincreasing in . Taking expectations and then the long-run limit proves the second claim. Finally the time change , together with multiplying cost by , converts rate and purchase cost into rate and purchase cost . Its expected cost is . □
Let be the objective value of any feasible solution of the program above.
Theorem 7.2 (Sharp coefficient for the LP certificate). For every feasible LP solution and every ,
The coefficient cannot be increased uniformly over the prescribed-resource instances and finite grids defined below. This is a sharpness assertion about the LP certificate, not about the competitive ratio of an online algorithm.
Proof. Fix a realized finite input. For each resource–scale pair , form a separate optimization problem with purchase cost and, for each original type- occurrence requiring , waiting weight . Zero-weight occurrences may be removed. Let its unrestricted optimum be . Any feasible original schedule induces a feasible schedule for each of these subproblems: serve an occurrence when the original schedule serves it and use the corresponding purchase of . Sum the subproblem costs. The budget pays for each resource purchase, and the budget pays for each request’s waiting. Taking the infimum over original schedules yields the pathwise bound
Fix a pair with . Independently retain each type- occurrence with probability and give every retained occurrence waiting weight . For any fixed schedule of the original weighted subproblem, the expected retained waiting is exactly its original weighted waiting. Apply its purchases to the retained input; purchases clearing no retained request can be deleted. The resulting expected cost is no larger than the original weighted schedule cost and is at least the expected retained optimum. Since the latter is independent of the chosen schedule, taking its infimum gives
This argument holds after fixing the input, even though the minimizing schedule is clairvoyant. Now average the input. Independent Poisson thinning and superposition make the retained process homogeneous. Normalize time by and cost by . The result is a unit-purchase, unit-waiting problem of rate
and horizon . Lemma 7.1 and its monotonicity assertion give
If or , the desired contribution is zero. Summing proves the full finite-horizon lower bound without a boundary loss or a restriction on the offline comparator.
For sharpness take one resource of cost and one type of rate . The finite grid below contains : its lower endpoint is at most , and its upper endpoint is at least . The feasible choice , zero elsewhere, has ; immediate service also supplies a dual solution of value , so . Time scaling makes the offline asymptotic cost rate exactly . Thus a larger uniform coefficient would fail as on this single-resource instance.
Using the exact probability of an empty clock tick
We now choose the scale grid and use the complete prefix information in the dual. Empty scheduled clearings incur no purchase cost.
Write and . Fix a grid ratio and a mean-budget parameter , and set
Form a finite LP grid from consecutive powers of . Its smallest scale is the largest such power at most , and its largest scale is the smallest such power at least
Here , , , and . The dual minimizes over nonnegative variables subject to
Solve these finite resource primal and dual programs on this grid and let their common optimum be . For an optimal dual put . Setting , , , and gives a feasible dual of value . Strong duality therefore implies
The cumulative information in the dual
For a resource , let . Sort its types by and regard each type as an interval of length carrying the constant value . This defines a nondecreasing rate quantile for . Put
The function is continuous, nonnegative, nondecreasing, convex, and piecewise linear. Both and are computable by sorting finitely many values and maximizing finitely many quadratic polynomials.
Lemma 7.3. For every used resource, .
Proof. Fix a grid scale with . Taking a fractional prefix of the sorted types gives numbers with
The type dual constraints and nonnegativity imply
Since , the resource constraint gives
The maximum defining is positive because as . Let attain it, and put . If , take . Otherwise, at every differentiability point,
Thus a maximizer satisfies . It follows that lies between the chosen grid endpoints. Round upward to the next grid scale . Then , including when itself is a grid scale. For , we have , and the grid-scale inequality gives
Here because .
The next lemma extracts a useful affine lower bound from the same maximizer.
Lemma 7.4. Let , , and let maximize . There is such that, on ,
Consequently, for every ,
Proof. Put . At an interior maximizer, the left and right derivatives of imply . Thus is a supporting slope for the convex function . If , the left derivative instead gives , which is a valid supporting slope on the domain . Therefore
Setting and using gives . Thus , and . The supporting line has slope and zero at . Combining it with proves the first assertion. Extend this nonnegative affine bound beyond and integrate its exponential over . The result is , which proves the second assertion.
Exact purchase rates for nested clocks
For a common , serve zero- types immediately and give every other type period
All clocks start at zero. At a tick, clear exactly the due nonempty type queues and purchase their required resource union. The periods are nested for every fixed . Let denote this rounding function for , with . It is nondecreasing in . For resource define
Lemma 7.5. The expected number of purchases of resource through is at most . For every fixed phase and every ,
where
Proof. Fix a resource and omit its subscript. Let be its total immediate rate and let be its distinct positive periods, with corresponding group rates . Put and . A tick of period that is not a tick of has exactly groups due. For each such group, its pending count comprises its arrivals since its preceding own clock tick, an interval of length . The counts of distinct types are independent, so the probability of a nonempty clearing is . These intervals lie in for every positive tick through . The nesting of the periods therefore gives the exact expectation
where the final floor with is defined to be zero. Immediate arrivals coincide with clock ticks only on a null event. Every coefficient in the last sum is nonnegative, so the expectation is at most
The last identity follows by integrating over each constant-period rate group; the initial zero-period segment contributes . It also covers .
After , each positive-period type has at most one final clearing, costing in total at most . Its expected waiting cost is at most . Summing proves the claimed finite-horizon inequality, including completion.
Averaging the common logarithmic shift
Lemma 7.6. For uniform ,
Proof. For , write . For every fixed positive , the rounding multiplier has the same distribution as with uniform on . The multipliers for different values of need not be independent.
Fix with . Use the weights on and the convexity of the exponential to obtain
Zero- terms have zero weight and are omitted. Averaging in uses only the identical one-dimensional multiplier distributions, yielding
If , then and the same inequality is an equality. Tonelli’s theorem and Lemma 7.4, with the same for every , now give
Here . Put . Completing the square gives for every real . As , this coefficient equals . The mean period is , so
The strict inequality follows from Lemma 7.3.
Selecting the phase. Test dyadic phases with successively finer certified evaluations and accept the first one for which is certified. At round , test the finite grid at precision , skipping any candidate whose rounding decisions are unresolved at that precision. This search uses only the instance and the dual scales . For evaluation, the preceding proof expresses every as a finite sum of exponentials; no numerical integration is required.
Lemma 7.7. The phase search terminates and returns .
Proof. Lemma 7.6 gives . The only possible discontinuities are the finitely many rounding breakpoints. Thus some open interval between them has , with a positive margin on a smaller interval. A dyadic phase lies in that smaller interval. At sufficiently high precision its rounding decisions and the strict comparison are certified, so the search stops. This proves finite termination, without asserting an efficient bound on the preprocessing time.
Theorem 7.8. For every fixed and , the preceding preprocessing and nested-clock policy define a deterministic causal algorithm satisfying
If the same LP has a valid finite-horizon lower certificate
with and a fixed finite , then
In particular its long-run ratio is at most . If the same positive coefficient is valid for all the grids obtained by varying , then for every a finite grid gives a ratio at most .
Proof. Use the phase from Lemma 7.7 in Lemma 7.5. The second assertion follows by rearranging the stated lower certificate. The completion constant is finite and depends only on the fixed instance. On a nontrivial instance , so it disappears in the long-run ratio. For the final assertion take and use the assumed uniformity of across these grids. The boundary constant may depend on the chosen grid, since that grid is fixed before the horizon tends to infinity. No finite grid is claimed to attain the limiting coefficient itself.
Theorem 7.9 (Prescribed-resource guarantee). For every and , the finite preprocessing and nested clocks above define a deterministic causal algorithm such that
In particular, and give ratio
The same guarantee holds for rooted and prescribed-pair aggregation on trees.
Proof. Combine Theorems 7.2 and 7.8. Appendix § 10 certifies . The positive series bounds from above and gives the strict displayed numerical inequality by rational arithmetic. On a nontrivial instance a positive feasible charge gives , so the offline lower bound is linear in and vanishes in the ratio. The path interpretations at the start of the section prove the tree consequences.
Polynomial-time preprocessing
Input and guarantee. Assume rational costs and rates in binary, fix rational and , and let be rational. Write for the total binary input length, including the encoding of . The construction below takes time polynomial in that length and . The all-free case is served immediately and bypasses the LP.
The LP grid. For a type , put , and let
The preceding grid contains consecutive powers of , starting at the last power at most and ending at the first power at least . For fixed rational , the logarithmic magnitudes of these endpoints are polynomial in . Thus the number of grid points, the absolute values of their exponents, and their rational encoding lengths are polynomial in . Exact comparisons of rational powers locate the endpoints without computing logarithms.
The resource primal and dual therefore have polynomially many variables and constraints with polynomial-size rational coefficients. Rational linear programming gives optimal rational solutions of polynomial encoding length in polynomial time. Let be their common value, and set for the selected optimal dual.
In a nontrivial instance, . Indeed, choose an incidence and a scale . Set and
with all other variables zero. This is a feasible primal solution of positive rational value. In particular, accuracy proportional to requires only polynomially many bits.
A finite rational phase grid
We use the preceding exact nested-clock rate bound. For a vector of nested periods , a zero period means immediate service. At resource , sort its users by period and let be the resulting rate-quantile function on , where . Put
The manuscript proves
These expressions retain the probability that a scheduled tick is empty.
Lemma 7.10 (Common scaling). For and ,
and consequently
Proof. The function is convex, nonnegative, and zero at the origin. Thus for , including when immediate types create an initial flat interval. Substitution gives
Increasing every period decreases each exponential integrand. Waiting scales linearly, yielding the two inequalities for .
Write and replace the phase by . For , define
For , set . Each positive type has exactly one possible breakpoint in this interval, namely the rational mantissa
The binary exponent and mantissa are computed by exact rational comparisons. At a breakpoint the exponent drops; the value at the breakpoint belongs to the cell to its right.
Set and form
There are candidates, all of polynomial encoding length. For any , take its largest predecessor . If there is nothing to prove. Otherwise there is no breakpoint in , so all exponents agree and
The predecessor is in the same rounding cell even if it is itself a breakpoint. No separation bound between distinct breakpoints is needed. Lemma 7.10 therefore gives
Lemma 7.6 supplies some with . We do not need a quantitative lower bound on the strict margin used in the original phase search.
Rational periods and certified candidate evaluation
Choose rational with . For example, rational bounds give
The positive series
has tail at most after terms. Refine these rational bounds until their induced upper and lower bounds for have ratio at most , and use the upper bound as . For fixed , this takes terms.
At each candidate use , with zero for immediate types. All periods are rational and nested. By common scaling and (7), some candidate satisfies
Compute a certified interval of width at most for each candidate, and choose the smallest upper endpoint. The chosen periods satisfy
because and for .
To verify the evaluation complexity, group equal positive periods at each resource as , with group rates , and put , . Then
All arguments and coefficients are rational of polynomial encoding length. Their total absolute coefficient size, together with the positive rational , determines a polynomial number of required accuracy bits. Tiny exponential differences need not be evaluated to small relative error.
For a nonnegative rational , can be enclosed to absolute error in polynomial time. If , use . Otherwise has polynomial magnitude; Taylor’s formula with its factorial remainder bound uses polynomially many rational operations to reach the requested accuracy. Interval operations then produce the required candidate bounds.
Finally, combine (6) with the preceding lower bound . Every positive-period type clears by its next finite tick, proving completion and the following theorem. The displayed boundary constant remains valid with the selected rational periods.
Theorem 7.11 (Efficient prescribed-resource guarantee). For fixed rational , and rational input, deterministic preprocessing polynomial in the input bit length and produces rational nested clocks satisfying
Here includes all completion costs and is independent of . With the parameters of Theorem 7.9 and , the ratio is below 2.113.
Proof. The finite candidate construction gives , where . Combine the exact clock bound with Theorem 7.2. The selected rational periods are finite, so every finite input completes. The preceding paragraphs establish polynomial encoding and computation. ∩ევნ
Rooted multi-level aggregation. Taking to be the path from a prescribed root to preserves both online and offline costs on every realized input. Hence the same 2.113 efficient guarantee applies to stochastic rooted MLA, improving on the general bound 210 reported by Mari, Pawlowski, Ren, and Sankowski [12]. This uses the new LP and clock policy and does not depend on, or establish correctness of, their GEN analysis. The running-time claim is a polynomial bit-complexity statement, not a strongly polynomial bound, and fixes the scale-grid parameters , .
Concluding remarks
Known Poisson rates permit a common schedule even when required resources overlap arbitrarily. The resource LP allocates purchase and waiting budgets without repeated charging; its dual coordinates the queues, including the possibility that a clock tick is empty. A finite rational phase grid makes preprocessing polynomial with an arbitrarily small multiplicative loss. The same result gives the improved rooted MLA bound by an exact path interpretation.
The competitive gap for general resources remains between and with finite preprocessing. The scalar family attains exactly , but this does not determine the answer for arbitrary resource sets. Closing the gap requires either a stronger algorithm for general overlap or an instance whose optimal causal-to-clairvoyant ratio exceeds the one-resource factor.
Further questions include exploiting tree structure beyond the generic resource guarantee, replacing the large fixed grid constants by a more practical optimization method, and learning unknown arrival rates. The model fixes those rates throughout execution; nonstationary demand requires a separate analysis.
Declaration of AI use
Generative AI tools (OpenAI’s Astra and Codex) assisted mathematical exploration, proof development, drafting and revision, literature searches, and LaTeX preparation. The authors are responsible for the correctness of the results and references and for the final text.
Scalar arithmetic certificates
Finite-state certificates for the exact scalar offline rate
Let denote the unrestricted offline cost per unit time for a rate-one Poisson process with setup cost and additive waiting. The cluster characterization in § 6.1 also gives
where is the exact consecutive-batch dynamic program. Indeed the regenerative clusters have geometric size and finite mean cost , and both the per-arrival and per-time rates equal because the original arrival rate is one. All comparisons below use this original per-arrival normalization. We never divide by the mean of the quantized gaps.
An exact finite state for integer gaps
First take an integer setup cost and integer gaps in . After arrivals, a candidate final batch containing requests has an excess cost above the current optimum . Retain only pairs with . A pair is discarded if another has no larger and no larger . When equal first coordinates occur, keep only the smaller excess. Store the remaining pairs with increasing and strictly decreasing . At least one retained pair has excess zero.
An excess is never needed again. At the next arrival, starting a singleton costs , while this old candidate costs at least even if the gap is zero. The singleton also has a smaller batch size, so the old candidate remains dominated after any further extension. The same comparison proves the Pareto deletion rule.
Every pending count can be replaced by . While subsequent gaps are zero, its magnitude has no effect on cost. At the first positive integer gap, such a candidate increases its cost by at least and is dominated by a new singleton. If equality occurs, the singleton has the smaller pending count. Thus this truncation remains valid even when arbitrarily many consecutive quantized gaps are zero. Equal truncated counts are again merged by taking the least excess.
For a new gap , the exact marginal cost is
Replace each old pair by
add the new singleton , and apply the deletion and merging rules above. Pairs with excess are deleted. This gives a deterministic transition . The initial state after the first request is . The stored coordinates lie in , so there are finitely many possible states. Breadth-first search enumerates precisely the states reachable from under the chosen alphabet. No queue-size restriction is imposed on the original instance.
If the gap has positive probability, it sends every state to . The resulting finite Markov chain therefore has a unique limiting distribution: two copies driven by the same gaps coalesce at their first occurrence of . If is its stochastic transition matrix and its expected one-step marginal cost, the exact long-run cost per arrival is
where . This also follows directly by telescoping and taking expected Cesaro averages.
Lower and upper quantizations of exponential gaps
In the continuous scalar problem, every gap at least can be made an optimal batch boundary. Consequently replacing by leaves every finite offline dynamic-programming value unchanged. Let be the number of bins, put , and define
The conditional mean within bin is .
For the lower quantization, given a capped gap in , set with probability and set with the remaining probability. Use independent rounding coins conditional on the original gaps. Thus for each original capped gap, not merely after averaging over its bin. For the atom , set . The resulting probabilities on the grid are
The final term includes the entire atom of the capped gap at . The setup cost becomes in units of , and the gap alphabet is .
For the upper quantization, condition on the bins and replace each finite-bin gap by its midpoint. The exponential density is decreasing, so . This follows, for example, by pairing and in the integral of over . The integer setup cost is now in units of . The gap alphabet is with probabilities .
The dynamic-programming value is the minimum of finitely many affine functions of the gaps. It is jointly concave and is nondecreasing in each gap. For every fixed , conditional Jensen therefore gives
The first inequality conditions on the original capped gaps and uses the mean-preserving endpoint randomization. The second conditions on the bins, applies Jensen at the conditional means, and then increases each mean to its midpoint. Dividing by and taking limits gives
These are comparisons of the unrestricted offline dynamic programs. The artificial grids are used only to bound costs; they do not define new physical arrival rates or restrict the original online policies.
A finite arithmetic certificate for the stationary reward
One need not approximate a stationary distribution. For any stochastic matrix on the enumerated states and its reward vector , put . For every integer ,
because . This inequality is exact at every fixed iteration count. Mixing rates are unnecessary for its validity.
The finite arithmetic certificate encloses every gap probability by exact rational numbers, then rounds them outward to multiples of . The lower probabilities need not sum to one, and neither do the upper probabilities. This causes no problem: all rewards and iterates are nonnegative. If and entrywise, then . An analogous inequality holds for upper bounds. Every multiplication and addition is rounded downward for lower bounds and upward for upper bounds. Consequently the minimum of its lower iterate is a rigorous lower bound on , and the maximum of its upper iterate is a rigorous upper bound.
All probability enclosures are produced using exact fractions. For , the alternating Taylor tails give
The terms are decreasing in magnitude throughout the relevant tail. The expression is decreasing in , which fixes the direction of the conditional-mean bounds. Products involving and are enclosed separately, so no independence or common extremizer of these interval endpoints is assumed.
Certified values
Both quantizations use bins. The endpoint graph has 59,666 states and 1,014,322 state–symbol transitions; the midpoint graph has 18,666 states and 317,322 transitions. Each has 17 input symbols. Using 100 directed iterations gives the following strict lower bounds. The graph is the same at each setup price; only the probability enclosures and cost scale change.
| lower bound on | |
| 0.6407995521894 | |
| 1 | 0.709707 |
| 0.886377 | |
| 1.1245989704271 | |
| 3 | 1.533777646201 |
| 6 | 2.375717698470 |
| 10 | 3.218954343659 |
Table 2.
The midpoint upper graph gives at setup one. This is a bound on the midpoint model; the next section corrects it to bound the original continuous-gap optimum more sharply. For arguments up to ten the probability generator uses alternating orders 80 and 81; the terms decrease in magnitude throughout the relevant tails. The source archive contains the graphs, exact probability generators, directed evaluator, and raw output for every displayed value.
The bounds at 3, 6, 10 imply the rational comparisons used in Theorem 6.7. For the resource upper bound, substitution of and the positive rational lower series for gives .
Conditional gap means and short clusters
We now use the conditional means inside the midpoint bins to improve the offline upper certificate. Let be the long-run offline cost per unit time of rate-one Poisson requests, unit additive delay, and a setup cost . For consecutive requests, write for their optimal completion cost when their interarrival gaps are . As proved in the scalar analysis, an optimum consists of consecutive batches served at their last arrival. Thus is the minimum of finitely many affine functions of the gap vector, and is concave and coordinatewise nondecreasing in that vector. Also for independent rate-one exponential gaps .
A finite-input correction of midpoint rounding
Fix , put , and cap gaps at one. On each interval , , round a gap to its midpoint ; map every gap at least one to one. Denote the resulting random gap vector by . Throughout this section the distribution of is fixed using this setup-one grid, even when is evaluated at a setup cost .
Conditional on an internal bin, the mean of an exponential gap is
Let be in each internal bin and one on the capped tail bin. For every , capping a gap at one does not change the optimum: an optimal schedule may cut at every gap at least . Conditional Jensen and monotonicity therefore give
Lemma A.1 (Mean correction using a second setup price). Fix , and put
Then
Proof. For each midpoint gap vector , choose an optimal setup-one partition with batches that cuts at every gap equal to one. Such a partition exists: splitting a batch at a gap of length one adds one setup but saves at least one unit of delay. Every uncut gap consequently belongs to an internal bin. Replacing by reduces the delay of this partition by times the number of requests preceding each uncut gap within its batch. There are uncut gaps, each with coefficient at least one. Hence
The same partition, evaluated at setup price , also gives
These two inequalities use the same fixed midpoint gap vector. Take expectations, use conditional Jensen for the setup-one cost, and use . The displayed claim follows.
Let be the cost rate of the midpoint model. The finite-state midpoint certificate already establishes this limit. Taking limits in the preceding finite-input inequality gives
No derivative of , interchange of perturbation limits, or numerical mixing-time estimate is used here. If and , this implies
When , a certified lower bound on suffices for a strict upper certificate on .
An additional nonnegative charge from short clusters
The exact coefficient of the gap shift for a partition with batch sizes is
The last sum is nonnegative. We can account for some of it without computing longer clusters or changing the finite-state graph. In the midpoint model, cut at every gap equal to one and call the resulting groups clusters. Within each cluster choose a minimum-cost partition, breaking ties by maximizing
These choices concatenate to a global minimum-cost partition. The earlier setup-price comparison holds for every minimum-cost partition, so this tie rule is compatible with the bound on . Write and for . For a cluster of size , let be the largest value of among optimal partitions with midpoint gaps . For every fixed cutoff , define
The two factors impose the preceding and following cluster boundaries. Thus is the expected retained extra charge per arrival in a stationary sequence of gaps. More explicitly, in an input of requests, each fixed size has possible cluster starts whose two boundary gaps are inside the input. Linearity of expectation gives a total expected extra charge at least . Clusters larger than have nonnegative extra charge and are simply omitted. No bound on their tail probabilities is needed.
Using this sharper coefficient in the same finite-input comparison and then taking proves
Equivalently, this is a feasible clairvoyant witness: choose the midpoint-optimal partition from the gap bins and serve each batch at its last actual arrival. Conditional on the bins, its expected cost is the cost with the conditional mean gaps, with the exact reduction . It completes every finite input.
A reproducible rational certificate
Use and . The midpoint graph has 18,666 states and gives the outward-rounded upper bound
The endpoint-rounding lower graph has 59,666 states. Evaluating that same graph with the exponential-bin probabilities for setup gives the conservative lower bound
This lower certificate uses its own grid with spacing . That grid is used only to bound the continuous quantity ; it is not identified with the fixed setup-one midpoint distribution in the finite-input lemma. For a completely rational bound on , put and
The positive exponential series gives , so
All quantities in the following comparison are rational:
before accounting for the additional short-cluster charge. For the additional charge, exact integer dynamic programming over all midpoint gap words with cluster size at most six gives
The four word counts for cluster sizes 3, 4, 5, 6 are respectively 256, 4096, 65536, and 1048576. Rescaling to setup cost 32 gives the integer midpoint gaps 1, 3, , 31, so all dynamic-programming comparisons and tie decisions are exact. Each exponential-bin probability and is enclosed using exact rational arithmetic. The nonnegative weighted sum is evaluated with downward rounding after every multiplication and addition, and its binary endpoint is converted to an exact fraction. Consequently the stronger rational certificate is
and
These strict comparisons are finite exact-rational calculations using the probability enclosures and directed iterations specified above. The ancillary files accompanying this arXiv version contain the verification programs, finite-state graphs, probability bounds, and complete arithmetic output. The file certificates/README.txt within the ancillary material gives the dependencies and commands needed to reproduce the numerical certificates. The programs verify the finite arithmetic bounds in this appendix; the probabilistic and algorithmic arguments are proved in the paper.
References
- [1]Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, and Shirley Zhang. Multi-level aggregation via dual fitting: An O(D)-competitive algorithm. arXiv preprint, 2026. arXiv:2608.04258.arxiv.org/abs/2608.04258
- [2]Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay—clairvoyance is not required. In 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ESA.2020.8.DOI
- [3]Yossi Azar and Liad Iluz. Beyond monotone delays for multi-level aggregation. In 34th Annual European Symposium on Algorithms (ESA 2026), volume 388 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1–65:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ESA.2026.65.DOI
- [4]Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 60–71. IEEE, 2019. arXiv:1904.07131, doi:10.1109/FOCS.2019.00013.DOI
- [5]Yossi Azar and Noam Touitou. Beyond tree embeddings—a deterministic framework for network design with deadlines or delay. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1368–1379. IEEE, 2020. arXiv:2004.07946, doi:10.1109/FOCS46700.2020.00129.DOI
- [6]Marcin Bienkowski, Martin Böhm, Jarosław Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, and Pavel Veselý. Online algorithms for multi-level aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ESA.2016.12.DOI
- [7]Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1235–1244. Society for Industrial and Applied Mathematics, 2017. doi:10.1137/1.9781611974782.80.DOI
- [8]Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. In LATIN 2018: Theoretical Informatics, pages 245–259. Springer, 2018. doi:10.1007/978-3-319-77404-6_19.DOI
- [9]Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e − 1). In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 502–509. Association for Computing Machinery, 2001. doi:10.1145/380752.380845.DOI
- [10]Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie. The power of clairvoyance for multi-level aggregation and set cover with delay. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1594–1610. Society for Industrial and Applied Mathematics, 2023. doi:10.1137/1.9781611977554.ch59.
- [11]Mathieu Mari, Michal Pawlowski, Runtian Ren, and Piotr Sankowski. Online matching with delays and stochastic arrival times. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 976–984. International Foundation for Autonomous Agents and Multiagent Systems, 2023. URL: https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p976.pdf, arXiv:2210.07018.arxiv.org/abs/2210.07018
- [12]Mathieu Mari, Michal Pawlowski, Runtian Ren, and Piotr Sankowski. Online multi-level aggregation with delays and stochastic arrivals. In 35th International Symposium on Algorithms and Computation (ISAAC 2024), volume 322 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ISAAC.2024.49.DOI
- [13]Jeremy McMahan. A D-competitive algorithm for the multilevel aggregation problem with deadlines. arXiv preprint, 2021. arXiv:2108.04422.arxiv.org/abs/2108.04422
- [14]Noam Touitou. Nearly-tight lower bounds for set cover and network design with deadlines/delay. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021), volume 212 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ISAAC.2021.53.DOI
- [15]Noam Touitou. Frameworks for nonclairvoyant network design with deadlines or delay. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.105.DOI