betaFeedback

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 tt units of time after its arrival incurs delay cost tt. 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 2.1132.113. 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 {e1,e2}\{e_1,e_2\}, {e2,e3}\{e_2,e_3\}, and {e1,e3}\{e_1,e_3\}, 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 2D2D bound for general delay in rooted aggregation depends on tree depth DD [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 e/(e−1)≈1.582e/(e - 1) \approx1.582 [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.

ProblemUpper boundLower 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 acknowledgmentOptimal 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.

Diagram showing Account for sharing costs across requests and resources; One common LP; What must any schedule pay?; One-resource comparisons; Lower bound on offline cost; Choose service times; Coordinate different types; Share resource purchases; Poisson TCP; Optimal online performance; Value of future information; Constant guarantee for arbitrary resource overlap; Efficient preprocessing

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 O(D42D)O(D^{4}2^{D}) guarantee for general delay on depth-DD trees [6]. For deadlines, Buchbinder, Feldman, Naor, and Talmon obtained O(D)O(D) [7], and McMahan obtained DD [13]. Azar and Touitou improved the general-delay bound to O(D2)O(D^{2}) [4]; Ahmadian and coauthors’ recent preprint gives 2D2D 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 O(log⁡m)O(\log m) 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 EE be a finite set of resources. Resource ee has purchase cost we>0w_e > 0, and w(S)=∑e∈Swew(S) = \sum_{e \in S} w_e for S⊆ES \subseteq E. There is a finite set II of request types. Each type ii has a prescribed nonempty resource set Ri⊆ER_i \subseteq E and arrival rate λi>0\lambda_i > 0. 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 x(r)x(r) for the type of request rr, a(r)a(r) for its arrival time, and t(r)≥a(r)t(r) \ge a(r) for its service time. A service chooses a batch BB of pending requests, purchases the union of their required resources, and serves them instantaneously. Its purchase cost is

w(⋃r∈BRx(r)).w\left(\bigcup_{r \in B} R_{x(r)}\right).

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 t(r)−a(r)t(r) - a(r). 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 ii are independent exponential variables of mean 1/λi1/\lambda_i. The rates are known before execution; the realized arrival times are revealed only as requests arrive.

For a horizon T>0T > 0, let ITI_T be the arrivals in [0,T][0,T]. The algorithm receives no signal that the input has ended. It must eventually serve all requests, and ALG⁡T\operatorname{ALG}_T includes the entire cost of doing so, even when some services occur after TT. Let OPT⁡T\operatorname{OPT}_T be the minimum cost of completing the same input. For a fixed instance we measure

RoE⁡(ALG⁡)=lim sup⁡T→∞E[ALG⁡T]E[OPT⁡T].(1)\operatorname{RoE}(\operatorname{ALG}) = \limsup_{T \to\infty} \frac{\mathbb{E}[\operatorname{ALG}_T]}{\mathbb{E}[\operatorname{OPT}_T]}. \tag*{(1)}

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 OI(1)O_I(1) for a finite constant that may depend on the fixed instance but not on TT.

The basic facts we will use

For a rate-λ\lambda process, an interval of fixed length pp contains λp\lambda p requests in expectation and is empty with probability e−λpe^{-\lambda p}. Counts in disjoint intervals are independent. Combining independent Poisson streams adds their rates; independently retaining each arrival with probability uu gives a Poisson stream of rate uλu\lambda. 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 pp are served at its end, their expected total waiting is

E[total waiting]=λ∫0p(p−t) dt=λp22.\mathbb{E}[\text{total waiting}] = \lambda\int_{0}^{p} (p-t)\,\mathrm{d}t = \frac{\lambda p^{2}}{2}.

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 ww and requests arriving at rate λ\lambda. 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 q=λwq=\lambda w expresses this tradeoff. By measuring time in units of 1/λ1/\lambda and multiplying all costs by λ\lambda, we obtain a rate-one process with purchase cost qq. Both cost rates and ratios are preserved. We use these units throughout this section.

Consider serving every nnth arrival, collecting nn requests per batch. The mean time from one completed batch to the next is nn. Each batch costs qq to purchase. While collecting it, the queue successively has 1,2,…,n−11,2,\ldots,n-1 waiting requests, and each next arrival takes one unit of time in expectation. Thus the mean waiting cost per batch is n(n−1)/2n(n-1)/2. Dividing the mean total cost by the mean cycle length gives

qn⏟purchase cost rate+n−12⏟waiting cost rate.\underbrace{\frac{q}{n}}_{\text{purchase cost rate}}+\underbrace{\frac{n-1}{2}}_{\text{waiting cost rate}}.

Choosing the best integer nn therefore gives the candidate rate

g(q)=min⁡n≥1{qn+n−12}.g(q)=\min_{n\geq1}\left\{\frac{q}{n}+\frac{n-1}{2}\right\}.

For q<1q<1 the best choice is immediate service; for 1<q<31<q<3 it is two requests per batch; for 3<q<63<q<6 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 g(q)g(q). 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 g(q)Tg(q)T 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 C(q)C(q) 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 qq can separate two optimal batches: an extra purchase costs qq, 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 C(q)C(q), 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 q>0q > 0, the optimal long-run ratio of expectations among all causal completing policies is g(q)/C(q)g(q)/C(q). A deterministic policy attains it. Over all positive loads,

sup⁡q>0g(q)C(q)=1C(1)≈1.409.\sup_{q>0} \frac{g(q)}{C(q)} = \frac{1}{C(1)} \approx1.409.

The load q=1q = 1 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 q=3q = 3 the optimal ratio is below 4/3, and at q=10q = 10 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 C(q)C(q) 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 CC 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 {a,b}\{a,b\} and another requires {b,c}\{b,c\}. Serving them together saves one purchase of bb. 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 {a,b}\{a,b\} may contribute some of its waiting cost to the aa pieces and the rest to the bb 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,

OPT⁡T≥∑piecesOPT⁡Tpiece.\operatorname{OPT}_{T} \ge\sum_{\text{pieces}} \operatorname{OPT}_{T}^{\text{piece}} .

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 L∗L^*. 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

h,2h,4h,8h,…h,\quad2h,\quad4h,\quad8h,\quad\ldots

with one common base hh 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 2h2h and 4h4h can share purchases at every multiple of 4h4h, 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 λi\lambda_i and period pip_i incurs long-run expected waiting cost λipi/2\lambda_i p_i/2. 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 λ\lambda and period pp, the probability that its queue is nonempty is 1−e−λp1-e^{-\lambda p}. The purchase cost rate for a resource of cost ww used by that type alone is therefore

wp(1−e−λp).\frac{w}{p}\left(1-e^{-\lambda p}\right).

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 L∗L^* 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 L∗L^*. With the selected parameters, their coefficients can be rounded outward to give the convenient bounds

E[OPTT]≥0.6565 L∗T,E[ALGT]≤1.3856 L∗T+O(1).\mathbb{E}[\mathrm{OPT}_T] \ge0.6565\,L^*T,\qquad\mathbb{E}[\mathrm{ALG}_T] \le1.3856\,L^*T+O(1).

Their ratio is below 2.111. The important point is that the size and overlap of the resource system enter through L∗L^* 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 z+=max⁡{z,0}z_{+} = \max\{z,0\} for the positive part, 1A\mathbf{1}_{A} for an event indicator, and ∣J∣\lvert J\rvert 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-λ\lambda process, the number N(J)N(J) of arrivals in an interval JJ has distribution

Pr⁡(N(J)=k)=e−λ∣J∣(λ∣J∣)kk!,E[N(J)]=Var⁡(N(J))=λ∣J∣.\Pr(N(J)=k)=e^{-\lambda\lvert J\rvert}\frac{(\lambda\lvert J\rvert)^k}{k!}, \qquad\mathbb{E}[N(J)]=\operatorname{Var}(N(J))=\lambda\lvert J\rvert.

Counts in disjoint intervals are independent. Conditional on nn arrivals in a finite interval, their unordered times are nn independent uniform points in that interval. In particular, for a nonnegative deterministic function gg,

E[∑ai∈[0,T]g(ai)]=λ∫0Tg(t) dt.(2)\mathbb{E}\left[\sum_{a_i\in[0,T]}g(a_i)\right]=\lambda\int_0^T g(t)\,\mathrm{d}t. \tag*{(2)}

Conditioning on the count proves this identity: the conditional expectation is nT−1∫0Tg(t) dtnT^{-1}\int_{0}^{T}g(t)\,\mathrm{d}t, and E[n]=λT\mathbb{E}[n]=\lambda T. We use it, for example, with g(t)g(t) 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 jj with probability qjq_j produces independent Poisson streams of rates qjλq_j\lambda. The generating function E[∏jzjNj]=exp⁡(λ∣J∣∑jqj(zj−1))\mathbb{E}\left[\prod_j z_j^{N_j}\right]=\exp\left(\lambda\lvert J\rvert\sum_j q_j(z_j-1)\right) 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 Pr⁡(N(J)=0)=e−λ∣J∣\Pr(N(J)=0)=e^{-\lambda\lvert J\rvert}. 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 xx, and let ux(a,J)u_x(a,J) be a nonnegative measurable quantity defined for a distinguished type-xx request at time aa and a finite multiset JJ of other requests. Then

E[∑i∈IT:xi=xux(ai,IT∖{i})]=λx∫0TE[ux(a,IT)] da.(3)\mathbb{E}\left[\sum_{\substack{i\in I_T:x_i=x}}u_x(a_i,I_T\setminus\{i\})\right]=\lambda_x\int_0^T\mathbb{E}[u_x(a,I_T)]\,\mathrm{d}a. \tag*{(3)}

On the right, ITI_T is an independent Poisson input to which the distinguished request can be added inside the definition of uxu_x.

Proof. Condition on the number Nx=nN_x=n of type-xx arrivals. Their times are independent uniforms in [0,T][0,T], and exchangeability makes the sum on the left equal in expectation to nn times the contribution of one distinguished uniform time, with n−1n-1 other type-xx times. The identity nPr⁡(Nx=n)=λxTPr⁡(Nx=n−1)n\Pr(N_x=n)=\lambda_xT\Pr(N_x=n-1) changes the latter n−1n-1 points back into an unconditional type-xx 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 Q(t)Q(t) for the pending-count vector, H(q)H(q) for its waiting rate, and LV(q)=∑iλi[V(q+ei)−V(q)]\mathcal{L}V(q)=\sum_i\lambda_i[V(q+e_i)-V(q)] for the arrival generator. At a service q→q′q\to q' of cost cc, call c+V(q′)−V(q)c+V(q')-V(q) its excess. Arrivals are inserted before their triggered services, as in our event convention.

Lemma 5.2. Let VV be bounded and nonnegative, with V(0)=0V(0)=0. For a causal policy starting empty,

E[cost⁡[0,T]+V(Q(T))]=E[∫0T(H+LV)(Q(t)) dt]+E[∑services through T[c+V(q′)−V(q)]].\mathbb{E}\left[\operatorname{cost}_{[0,T]}+V(Q(T))\right] = \mathbb{E}\left[\int_0^T(H+\mathcal{L}V)(Q(t))\,\mathrm{d}t\right] + \mathbb{E}\left[\sum_{\text{services through }T}\left[c+V(q')-V(q)\right]\right].

Here cost⁡[0,T]\operatorname{cost}_{[0,T]} includes only costs incurred through TT. If H+LV≥gH+\mathcal{L}V\ge g in every state and every service has nonnegative excess, then every causal completing policy satisfies E[ALGT]≥gT\mathbb{E}[\mathrm{ALG}_T]\ge gT, including randomized policies and partial services.

Proof. Telescope the potential over arrivals and services. Conditional Poisson compensation replaces the arrival increments by ∫0TLV(Q(t)) dt\int_0^T \mathcal{L}V(Q(t))\,\mathrm{d}t; independent policy coins are included in the history. Boundedness permits localization for policies of finite expected cost. The lower-bound hypotheses give E[cost⁡[0,T]+V(Q(T))]≥gT\mathbb{E}[\operatorname{cost}_{[0,T]}+V(Q(T))]\ge gT. After the last arrival, the service inequalities telescope from V(Q(T))V(Q(T)) to V(0)=0V(0)=0, 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 VV as above and unit waiting per request, suppose an untimed policy has at most nn pending requests between events, (H+LV)(q)≤g(H+\mathcal{L}V)(q)\le g 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 b≥0b\ge0. Conditional on the past at each busy-period start, its untimed duration SS satisfies Pr⁡(S>t∣past)≤Be−ηt\Pr(S>t\mid\text{past})\le Be^{-\eta t} for t≥0t\ge0, where η>0\eta>0 and B≥1B\ge1. Suppose the expected number of starts through TT is at most νT\nu T. Clear period mm at its normal end or at the earlier deadline

Hm=ln⁡B+2ln⁡(m+1)η.H_m=\frac{\ln B+2\ln(m+1)}{\eta}.

Then every finite input completes without an end signal, and

E[ALGT]≤gT+2b+nη[ln⁡B+2ln⁡(νT+1)].\mathbb{E}[\mathrm{ALG}_T]\le gT+2b+\frac{n}{\eta}\left[\ln B+2\ln(\nu T+1)\right].

Proof. The tail bound makes the conditional probability of timeout mm at most (m+1)−2(m+1)^{-2}. Their sum is less than one. The accounting identity gives E[cost⁡[0,T]+V(Q(T))]≤gT+b\mathbb{E}[\operatorname{cost}_{[0,T]}+V(Q(T))]\le gT+b on an infinite continuation. The truncated input has the same prefix. If period mm is pending at TT, it clears by its deadline, paying at most V(Q(T))+b+nHmV(Q(T))+b+nH_m afterward. Its index is at most the number of starts through TT. 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 ww and arrival rate λ\lambda, put q=λwq=\lambda w. The time change t↦λtt\mapsto\lambda t, together with multiplication of cost by λ\lambda, gives rate one and setup cost qq. 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 λ\lambda when returning to the original units.

The exact unrestricted offline rate

For nn arrivals at times a1=0<a2<⋯<ana_1=0<a_2<\cdots<a_n, write xj=aj+1−ajx_j=a_{j+1}-a_j. Define D0=0D_0=0 and, for 1≤j≤n1\le j\le n,

Dj(q;x1,…,xj−1)=min⁡0≤k<j{Dk+q+∑r=k+1j−1(r−k)xr}.D_j(q;x_1,\ldots,x_{j-1})=\min_{0\le k<j}\left\{D_k+q+\sum_{r=k+1}^{j-1}(r-k)x_r\right\}.

An empty sum is zero. Thus D1=qD_1=q, and the cost of serving three arrivals in one batch is q+x1+2x2q+x_1+2x_2. The factor on a gap is the number of requests already waiting while that gap elapses.

Lemma 6.1. The dynamic program DnD_n gives the unrestricted offline optimum for these nn arrivals. Moreover, any gap of length at least qq 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 kk has exactly the cost displayed in the recurrence, proving completeness of the dynamic program.

Suppose one such batch spans a gap xj≥qx_j \ge q. Split it at that gap and serve its earlier part at the last arrival of that part. The extra purchase costs qq, whereas at least one earlier request avoids waiting for the entire gap, saving at least qq. The split therefore cannot increase cost. Repeating the operation establishes the second assertion. □

Put p=e−qp=e^{-q} and r=1−pr=1-p. Consecutive arrivals separated by gaps smaller than qq form a cluster; a gap at least qq separates clusters. For a cluster beginning at a specified arrival, its number of arrivals NN has distribution

Pr⁡(N=n)=prn−1,n≥1.\Pr(N=n)=pr^{n-1},\qquad n\ge1.

Conditional on N=nN=n, the internal gaps are independent exponential variables conditioned to belong to [0,q)[0,q). Their joint density is e−∑jxj/rn−1e^{-\sum_{j}x_j}/r^{n-1} on that cube. The exact cost rate is described by the following absolutely convergent series of finite-dimensional integrals.

Theorem 6.2. For every q>0q>0, define

C(q)=p2∑n=1∞∫[0,q]n−1Dn(q;x1,…,xn−1)e−∑j=1n−1xj dx1⋯dxn−1.C(q)=p^2\sum_{n=1}^{\infty}\int_{[0,q]^{n-1}}D_n(q;x_1,\ldots,x_{n-1})e^{-\sum_{j=1}^{n-1}x_j}\,dx_1\cdots dx_{n-1}.

For n=1n=1, the integral denotes the number qq. Then the unrestricted offline optimum satisfies

∣E[OPTT]−C(q)T∣≤4qeq(T≥0).\left|\mathbb{E}[\mathrm{OPT}_T]-C(q)T\right|\le4qe^q\qquad(T\ge0).

In particular its expected long-run cost rate exists and equals C(q)C(q). If CK(q)C_K(q) denotes the series truncated at n=Kn=K, then

0≤C(q)−CK(q)≤qrK(1+Kp).0\le C(q)-C_K(q)\le qr^K(1+Kp).

Also qp2≤C(q)≤qqp^2\le C(q)\le q.

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 qq. This event has probability pp and is independent of the entire future cluster. Thus cluster starts have intensity pp. If DD denotes the cost of a whole cluster beginning at a distinguished arrival, the Poisson insertion identity gives

E[∑cluster starts s∈[0,T]D(cluster at s)]=TpE[D].(4)\mathbb{E}\left[\sum_{\substack{\text{cluster starts }s\in[0,T]}}D(\text{cluster at }s)\right]=Tp\mathbb{E}[D]. \tag*{(4)}

This application can be reduced to the finite-window insertion identity: truncate each cluster after its first KK arrivals. The resulting quantity depends only on the Poisson configuration in [−q,T+Kq][-q,T+Kq]. Let K→∞K \to\infty. Deleting requests cannot increase optimum cost, so the truncated costs increase to DD, and monotone convergence applies. Also D≤qND \le qN and E[N]=1/p\mathbb{E}[N] = 1/p, ensuring integrability.

Conditioning on NN and its internal gaps gives

pE[D]=p2∑n≥1∫[0,q]n−1Dne−∑jxj dx=C(q).p\mathbb{E}[D] = p^2 \sum_{n \ge1} \int_{[0,q]^{n-1}} D_n e^{-\sum_j x_j}\,dx = C(q).

All clusters wholly inside [0,T][0,T] contribute exactly the same amount to this stationary reward sum and to OPTT\mathrm{OPT}_T. Only clusters crossing 00 or TT can contribute a difference. Deleting arrivals from a cluster cannot increase its optimal cost, and its full cost is at most qq times its full size. At any deterministic boundary, the size of a cluster crossing it is bounded by the sum of two geometric(pp) 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 qq. Each count has expectation 1/p1/p. If the gap straddling the boundary is itself at least qq, there is no crossing cluster and its contribution is zero. Hence the expected size charged at a boundary is at most 2/p2/p. The two boundaries together yield

∣E[OPTT]−TpE[D]∣≤4qp=4qeq.\left|\mathbb{E}[\mathrm{OPT}_T] - Tp\mathbb{E}[D]\right| \le\frac{4q}{p} = 4qe^q.

The same estimate covers the case where one cluster crosses both boundaries, since counting it twice only enlarges the bound.

Finally q≤Dn≤nqq \le D_n \le nq for every nonempty cluster. In particular the first series term gives C(q)≥qp2>0C(q) \ge qp^2 > 0. The upper bounds imply C(q)≤qC(q) \le q and

C(q)−CK(q)≤p2q∑n=K+1∞nrn−1=qrK((K+1)p+r)=qrK(1+Kp).\begin{aligned} C(q) - C_K(q) \le p^2q \sum_{n=K+1}^{\infty} nr^{n-1} \\ &= qr^K\bigl((K+1)p+r\bigr) = qr^K(1+Kp). \end{aligned}

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

Define

g(q)=min⁡n≥1{qn+n−12}.g(q) = \min_{n \ge1}\left\{\frac{q}{n}+\frac{n-1}{2}\right\}.

Choose an integer N≥1N \ge1 with

N(N−1)2≤q≤N(N+1)2.\frac{N(N-1)}{2} \le q \le\frac{N(N+1)}{2}.

Then g(q)=q/N+(N−1)/2g(q)=q/N+(N-1)/2 and N−1≤g(q)≤NN-1 \le g(q) \le N. At a common endpoint either adjacent choice is valid. These facts follow by comparing consecutive terms: their difference is 1/2−q/[n(n+1)]1/2-q/[n(n+1)].

Theorem 6.3. For every q>0q > 0, every causal completing policy, including randomized policies and policies using partial batches, satisfies

E[ALGT]≥g(q)T(T≥0).\mathbb{E}[\mathrm{ALG}_T] \ge g(q)T \qquad(T \ge0).

There is a deterministic horizon-unaware policy that completes every finite input and has expected cost rate exactly g(q)g(q). For N≥2N \ge2, it satisfies the explicit bound

E[ALGT]≤g(q)T+2q+(N−1)[2(N−1)ln⁡2+4ln⁡(T+1)].\mathbb{E}[\mathrm{ALG}_T] \le g(q)T + 2q + (N-1)\left[2(N-1)\ln2 + 4\ln(T+1)\right].

For N=1N=1, immediate service has expected cost exactly qTqT.

Proof. Write g=g(q)g=g(q) and define

hq(n)={ng−n(n−1)/2,0≤n≤N,q,n≥N.h_q(n)= \begin{cases} ng-n(n-1)/2, & 0\le n\le N,\\ q, & n\ge N. \end{cases}

The formulas agree at NN. Since N−1≤g≤NN-1\le g\le N, the potential is nondecreasing and lies in [0,q][0,q]. Moreover,

n+hq(n+1)−hq(n)≥g,n+h_q(n+1)-h_q(n)\ge g,

with equality for n<Nn<N. Every service costs qq and lowers hqh_q by at most qq, including a partial clearing. Lemma 5.2 proves the all-causal lower bound.

For the upper bound, serve immediately when N=1N=1. Otherwise clear a batch at its NNth arrival or at the deadline

Hm=2(N−1)ln⁡2+4ln⁡(m+1)H_m=2(N-1)\ln2+4\ln(m+1)

after the first arrival of its mmth batch. Between events the queue has at most N−1N-1 requests and drift plus holding exactly gg. A full batch costs its potential decrease hq(N)=qh_q(N)=q; a timeout has excess at most qq. The untimed wait for N−1N-1 new arrivals satisfies E[eS/2]=2N−1\mathbb{E}[e^{S/2}]=2^{N-1}, hence Pr⁡(S>t)≤2N−1e−t/2\Pr(S>t)\le2^{N-1}e^{-t/2}. At most one batch starts per arrival. Lemma 5.3, with (n,b,η,B,ν)=(N−1,q,1/2,2N−1,1)(n,b,\eta,B,\nu)=(N-1,q,1/2,2^{N-1},1), gives precisely the stated finite-horizon bound. Its excess is O(ln⁡(T+1))O(\ln(T+1)), proving attainment of gg with full completion.

Corollary 6.4. For every q>0q>0, the smallest long-run ratio of expectations among causal completing policies is exactly g(q)/C(q)g(q)/C(q). 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 C(q)>0C(q)>0. Divide the finite-horizon lower bound and the attaining policy’s asymptotic equality by E[OPTT]\mathbb{E}[\mathrm{OPT}_T].

Two structural properties of the scalar offline rate

Lemma 6.5. The function CC is concave on [0,∞)[0,\infty), with C(0)=0C(0)=0. Writing qn=n(n+1)/2q_n=n(n+1)/2, one has

sup⁡q>0g(q)C(q)=sup⁡n≥1nC(qn).\sup_{q>0}\frac{g(q)}{C(q)}=\sup_{n\ge1}\frac{n}{C(q_n)}.

Proof. For each fixed arrival realization, the offline cost is the infimum over schedules of qq times the number of services plus their waiting cost. It is therefore concave in qq. Taking expectations, dividing by the horizon, and passing to the existing cost-rate limit preserves concavity. The free-setup problem has zero cost, and 0≤C(q)≤q0\le C(q)\le q, so the extension at zero is valid.

On [qn−1,qn][q_{n-1},q_n], the function gg is affine with endpoint values n−1,nn-1,n. Concavity lower-bounds CC by the chord between the same endpoints. It follows that C(q)/g(q)C(q)/g(q) is at least the smaller endpoint ratio. For the first interval (0,1](0,1], use C(q)≥qC(1)C(q) \ge qC(1) and g(q)=qg(q)=q instead of forming the undefined ratio at zero. Every positive qq belongs to one of these intervals, proving the supremum identity.

Lemma 6.6. For s≥1s \ge1 and q>0q > 0,

C(s2q)≥sC(q).C(s^{2}q) \ge sC(q).

Equivalently C(q)/qC(q)/\sqrt{q} is nondecreasing.

Proof. Let JJ be a finite realized set of arrival slots, and define

FJ(z)=inf⁡S completes every slot of J{q#services(S)+∑i∈JziWi(S)},zi≥0.F_J(z)=\inf_{\substack{S\ \text{completes every slot of }J}}\left\{q\mathbin{\#}\mathrm{services}(S)+\sum_{i\in J}z_iW_i(S)\right\},\qquad z_i\ge0.

The feasible family is fixed, including when some ziz_i are zero. Thus FJF_J is concave as an infimum of affine functions of zz. Independently retain each slot with probability 1/s1/s, writing BiB_i for its retention indicator and JBJ_B for the retained input. Conditional Jensen gives

FJ(1/s)≥EB[FJ(B)]≥EB[OPT⁡q(JB)].F_J(1/s)\ge\mathbb{E}_B[F_J(B)]\ge\mathbb{E}_B[\operatorname{OPT}_q(J_B)].

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 JJ be a rate-ss Poisson input in [0,T][0,T]. Its independently retained subset has rate one. Factoring 1/s1/s out of the objective gives FJ(1/s)=s−1OPT⁡sq(J)F_J(1/s)=s^{-1}\operatorname{OPT}_{sq}(J). Consequently, for every finite horizon including completion,

1sE[OPT⁡λ=s,w=sq,T]≥E[OPT⁡λ=1,w=q,T].\frac{1}{s}\mathbb{E}[\operatorname{OPT}_{\lambda=s,w=sq,T}]\ge\mathbb{E}[\operatorname{OPT}_{\lambda=1,w=q,T}].

The normalized scalar cost rate for parameters (λ,w)(\lambda,w) is C(λw)C(\lambda w). Divide by TT 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:

C(1)<57,C(3)>32,C(6)>94,C(10)>165.C(1)<\frac{5}{7},\qquad C(3)>\frac{3}{2},\qquad C(6)>\frac{9}{4},\qquad C(10)>\frac{16}{5}.

Theorem 6.7. The optimal competitive factor over all positive-rate, positive-setup single-resource instances is exactly

sup⁡q>0g(q)C(q)=1C(1).\sup_{q>0}\frac{g(q)}{C(q)}=\frac{1}{C(1)}.

The load q=1q=1 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,

C(3)>32>257>2C(1),C(6)>94>357>3C(1).(5)C(3)>\frac{3}{2}>2\frac{5}{7}>2C(1),\qquad C(6)>\frac{9}{4}>3\frac{5}{7}>3C(1). \tag*{(5)}

Furthermore

(165)2−20(57)2=441225>0,\left(\frac{16}{5}\right)^2 - 20\left(\frac{5}{7}\right)^2 = \frac{44}{1225} > 0,

so C(10)>20C(1)C(10) > \sqrt{20} C(1). For every n≥4n \ge4, the triangular load qn≥10q_n \ge10 satisfies, by Lemma 6.6,

C(qn)≥qn/10 C(10)>2qn C(1)=n(n+1) C(1)>nC(1).C(q_n) \ge\sqrt{q_n/10}\,C(10) > \sqrt{2q_n}\,C(1) = \sqrt{n(n+1)}\,C(1) > nC(1).

Thus every triangular load after the first has a strictly smaller ratio than 1/C(1)1/C(1). Lemma 6.5 controls every intervening load. At q=1q = 1, g(1)=1g(1) = 1, 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

0.709707<C(1)<0.710122517893,1.4082077033<1C(1)<1.40904.0.709707 < C(1) < 0.710122517893,\qquad1.4082077033 < \frac{1}{C(1)} < 1.40904.

The lower bound on C(1)C(1) controls the upper end of the scalar factor; the upper bound on C(1)C(1) 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 1/C(1)>1.40820770331/C(1) > 1.4082077033. 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 TT in expectation by Theorem 6.3, while the offline cost rate is C(1)C(1). 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 Rresource∗R^*_{\mathrm{resource}} obeys

1.4082077033<Rresource∗<2.110250205.1.4082077033 < R^*_{\mathrm{resource}} < 2.110250205.

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 e∈Ee \in E has purchase cost wew_e, and type i∈Ii \in I requires Ri⊆ER_i \subseteq E and arrives at rate λi\lambda_i. 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, RiR_i is the unique path between the two endpoints of type ii. 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 xx and set RxR_x 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 A\mathcal{A} be a finite set of positive time scales and fix β>0\beta> 0. For each resource–scale pair use a purchase budget ceac_{ea}, and for each incidence e∈Rie \in R_i use a charge δiea\delta_{iea}. The program has objective

L∗=max⁡∑i,e∈Ri,a∈AλiδieaL^* = \max\sum_{i,e\in R_i,a\in\mathcal{A}} \lambda_i\delta_{iea}

and nonnegative variables satisfying

∑e∈Ri,aδieaa≤1,δiea≤cea,a∑i:e∈Riλiδiea≤βcea,∑acea≤we.\sum_{e\in R_i,a} \frac{\delta_{iea}}{a} \le1,\qquad\delta_{iea} \le c_{ea},\qquad a\sum_{i:e\in R_i}\lambda_i\delta_{iea} \le\beta c_{ea},\qquad\sum_a c_{ea} \le w_e.

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

E[OPTT]≥C(β)βL∗T,E[ALGT]≤(r+Dβ)L∗T+KI,D=14(ln⁡2)2.\mathbb{E}[\mathrm{OPT}_T] \ge\frac{C(\beta)}{\beta}L^*T,\qquad\mathbb{E}[\mathrm{ALG}_T] \le\left(r+\frac{D}{\beta}\right)L^*T+K_I,\qquad D=\frac{1}{4(\ln2)^2}.

Here r>1r>1 will be the finite grid ratio, and KIK_I 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 Fq(T)F_q(T) be the expected unrestricted offline batching cost on [0,T][0,T], with purchase cost q>0q>0 and unit waiting cost. Define

C(q)=lim⁡T→∞Fq(T)T.C(q)=\lim_{T\to\infty}\frac{F_q(T)}{T}.

The exact convergent series and existence of this limit are proved in § 6.1. In particular 0<C(q)≤q0<C(q)\le q.

Lemma 7.1. For every q,T>0q,T>0, Fq(T)≥C(q)TF_q(T)\ge C(q)T. The ratio C(q)/qC(q)/q is nonincreasing in qq. For a rate-uu Poisson process with unit purchase cost and unit waiting cost, its expected offline cost on [0,H][0,H] 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 Fq(S+T)≤Fq(S)+Fq(T)F_q(S+T)\le F_q(S)+F_q(T). For any positive integer nn, Fq(nT)≤nFq(T)F_q(nT)\le nF_q(T). Divide by nTnT and use the defining limit to obtain the first claim.

For each fixed finite input, its optimum divided by qq equals

inf⁡S{number of purchases in S+total waiting in Sq}.\inf_{\mathcal{S}}\left\{\text{number of purchases in }\mathcal{S}+\frac{\text{total waiting in }\mathcal{S}}{q}\right\}.

This quantity is nonincreasing in qq. Taking expectations and then the long-run limit proves the second claim. Finally the time change t′=utt'=ut, together with multiplying cost by uu, converts rate uu and purchase cost 11 into rate 11 and purchase cost uu. Its expected cost is Fu(uH)/u≥C(u)HF_u(uH)/u\ge C(u)H. □

Let LL 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 T≥0T\ge0,

E[OPT⁡T]≥C(β)βLT.\mathbb{E}[\operatorname{OPT}_T]\ge\frac{C(\beta)}{\beta}LT.

The coefficient C(β)/βC(\beta)/\beta 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 (e,a)(e,a), form a separate optimization problem with purchase cost ceac_{ea} and, for each original type-ii occurrence requiring ee, waiting weight δiea/a\delta_{iea}/a. Zero-weight occurrences may be removed. Let its unrestricted optimum be OeaO_{ea}. 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 ee. Sum the subproblem costs. The budget ∑acea≤we\sum_a c_{ea}\le w_e pays for each resource purchase, and the budget ∑e∈Ri,aδiea/a≤1\sum_{e\in R_i,a}\delta_{iea}/a\le1 pays for each request’s waiting. Taking the infimum over original schedules yields the pathwise bound

OPT⁡T≥∑e,aOea.\operatorname{OPT}_T\ge\sum_{e,a}O_{ea}.

Fix a pair with c=cea>0c=c_{ea}>0. Independently retain each type-ii occurrence with probability δiea/c\delta_{iea}/c and give every retained occurrence waiting weight c/ac/a. 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

Oea≥Ethinning[Oearetained].O_{ea}\ge\mathbb{E}_{\mathrm{thinning}}\left[O_{ea}^{\mathrm{retained}}\right].

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 aa and cost by cc. The result is a unit-purchase, unit-waiting problem of rate

u=ac∑iλiδiea≤βu=\frac{a}{c}\sum_i\lambda_i\delta_{iea}\le\beta

and horizon H=T/aH=T/a. Lemma 7.1 and its monotonicity assertion give

E[Oea]≥cC(u)Ta≥C(β)βT∑iλiδiea.\mathbb{E}[O_{ea}]\ge cC(u)\frac{T}{a}\ge\frac{C(\beta)}{\beta}T\sum_i\lambda_i\delta_{iea}.

If c=0c=0 or u=0u=0, 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 11 and one type of rate λ=β\lambda=\beta. The finite grid below contains a=1a=1: its lower endpoint is at most 1/21/2, and its upper endpoint is at least 22. The feasible choice δe,1,1=ce,1=1\delta_{e,1,1}=c_{e,1}=1, zero elsewhere, has L=βL=\beta; immediate service also supplies a dual solution of value β\beta, so L∗=βL^*=\beta. Time scaling makes the offline asymptotic cost rate exactly C(β)C(\beta). Thus a larger uniform coefficient would fail as T→∞T\to\infty 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 ℓ=ln⁡2\ell=\ln2 and D=1/(4ℓ2)D=1/(4\ell^2). Fix a grid ratio r>1r>1 and a mean-budget parameter β>0\beta>0, and set

K=r+D/β,s=2ℓK.K=r+D/\beta,\qquad s=2\ell K.

Form a finite LP grid from consecutive powers of rr. Its smallest scale is the largest such power at most β/(2Γ)\beta/(2\Gamma), and its largest scale is the smallest such power at least

max⁡{2M/λmin⁡,β/λmin⁡}.\max\{2M/\lambda_{\min},\beta/\lambda_{\min}\}.

Here Γ=∑iλi\Gamma=\sum_i\lambda_i, λmin⁡=min⁡iλi\lambda_{\min}=\min_i\lambda_i, Ci=∑e∈RiweC_i=\sum_{e\in R_i}w_e, and M=∑iλiCiM=\sum_i\lambda_iC_i. The dual minimizes ∑iyi+∑eweze\sum_i y_i+\sum_e w_ez_e over nonnegative variables subject to

yi/a+siea+aλitea≥λi,ze≥βtea+∑i:e∈Risiea.y_i/a+s_{iea}+a\lambda_i t_{ea}\ge\lambda_i,\qquad z_e\ge\beta t_{ea}+\sum_{i:e\in R_i}s_{iea}.

Solve these finite resource primal and dual programs on this grid and let their common optimum be L∗L^*. For an optimal dual put τi=yi/λi\tau_i=y_i/\lambda_i. Setting yi=0y_i=0, tea=0t_{ea}=0, siea=λis_{iea}=\lambda_i, and ze=Λez_e=\Lambda_e gives a feasible dual of value MM. Strong duality therefore implies

L∗≤M,0≤τi≤M/λmin⁡.L^*\le M,\qquad0\le\tau_i\le M/\lambda_{\min}.

The cumulative information in the dual

For a resource ee, let Λe=∑i:e∈Riλi\Lambda_e=\sum_{i:e\in R_i}\lambda_i. Sort its types by τi\tau_i and regard each type as an interval of length λi\lambda_i carrying the constant value τi\tau_i. This defines a nondecreasing rate quantile τe(v)\tau_e(v) for 0<v<Λe0<v<\Lambda_e. Put

Ge(v)=∫0vτe(u) du,Ze=max⁡0≤v≤Λev(1−Ge(v)/β).G_e(v)=\int_0^v\tau_e(u)\,du,\qquad Z_e=\max_{0\le v\le\Lambda_e}v\left(1-G_e(v)/\beta\right).

The function GeG_e is continuous, nonnegative, nondecreasing, convex, and piecewise linear. Both GeG_e and ZeZ_e are computable by sorting finitely many values and maximizing finitely many quadratic polynomials.

Lemma 7.3. For every used resource, 0<Ze<rze0<Z_e<rz_e.

Proof. Fix a grid scale aa with v=β/a≤Λev=\beta/a\le\Lambda_e. Taking a fractional prefix of the sorted types gives numbers αi∈[0,1]\alpha_i\in[0,1] with

∑iαiλi=v,∑iαiλiτi=Ge(v).\sum_i\alpha_i\lambda_i=v,\qquad \sum_i\alpha_i\lambda_i\tau_i=G_e(v).

The type dual constraints and nonnegativity imply

∑isiea≥∑iαisiea≥v−Ge(v)/a−avtea.\sum_i s_{iea}\ge\sum_i\alpha_i s_{iea}\ge v-G_e(v)/a-avt_{ea}.

Since av=βav=\beta, the resource constraint gives

ze≥βtea+∑isiea≥v(1−Ge(v)/β).z_e \ge\beta t_{e a}+\sum_i s_{iea}\ge v(1-G_e(v)/\beta).

The maximum defining ZeZ_e is positive because Ge(v)→0G_e(v)\to0 as v↓0v\downarrow0. Let v∗>0v_*>0 attain it, and put τmax⁡,e=max⁡i:e∈Riτi\tau_{\max,e}=\max_{i:e\in R_i}\tau_i. If τmax⁡,e=0\tau_{\max,e}=0, take v∗=Λev_*=\Lambda_e. Otherwise, at every differentiability point,

ddv[v(1−Ge(v)/β)]=1−Ge(v)/β−vτe(v)/β≥1−2vτmax⁡,e/β.\frac{d}{dv}\left[v(1-G_e(v)/\beta)\right]=1-G_e(v)/\beta-v\tau_e(v)/\beta\ge1-2v\tau_{\max,e}/\beta.

Thus a maximizer satisfies v∗≥min⁡{Λe,β/(2τmax⁡,e)}v_*\ge\min\{\Lambda_e,\beta/(2\tau_{\max,e})\}. It follows that a∗=β/v∗a_*=\beta/v_* lies between the chosen grid endpoints. Round a∗a_* upward to the next grid scale a′a'. Then a∗≤a′<ra∗a_*\le a'<ra_*, including when a∗a_* itself is a grid scale. For v′=β/a′v'=\beta/a', we have v∗/r<v′≤v∗v_*/r<v'\le v_*, and the grid-scale inequality gives

ze≥v′(1−Ge(v′)/β)≥v′(1−Ge(v∗)/β)>v∗r(1−Ge(v∗)/β)=Ze/r.z_e\ge v'(1-G_e(v')/\beta)\ge v'(1-G_e(v_*)/\beta)>\frac{v_*}{r}(1-G_e(v_*)/\beta)=Z_e/r.

Here 1−Ge(v∗)/β>01-G_e(v_*)/\beta>0 because Ze>0Z_e>0.

The next lemma extracts a useful affine lower bound from the same maximizer.

Lemma 7.4. Let G=GeG=G_e, Z=ZeZ=Z_e, and let v∗>0v_*>0 maximize v(1−G(v)/β)v(1-G(v)/\beta). There is h=v∗/Z∈[1,2]h=v_*/Z\in[1,2] such that, on [0,Λe][0,\Lambda_e],

G(v)≥βmax⁡{0,v−aZh2},a=Z(2h−h2)≥0.G(v)\ge\beta\max\left\{0,\frac{v-a}{Zh^2}\right\},\qquad a=Z(2h-h^2)\ge0.

Consequently, for every q>0q>0,

∫0Λee−qG(v) dv≤Z(2h−h2+h2qβ).\int_0^{\Lambda_e}e^{-qG(v)}\,dv\le Z\left(2h-h^2+\frac{h^2}{q\beta}\right).

Proof. Put g=(β−G(v∗))/v∗=βZ/v∗2>0g=(\beta-G(v_*))/v_*=\beta Z/v_*^2>0. At an interior maximizer, the left and right derivatives of v(1−G(v)/β)v(1-G(v)/\beta) imply G−′(v∗)≤g≤G+′(v∗)G'_-(v_*)\le g\le G'_+(v_*). Thus gg is a supporting slope for the convex function GG. If v∗=Λev_*=\Lambda_e, the left derivative instead gives g≥G−′(v∗)g\ge G'_-(v_*), which is a valid supporting slope on the domain [0,Λe][0,\Lambda_e]. Therefore

G(v)≥G(v∗)+g(v−v∗).G(v)\ge G(v_*)+g(v-v_*).

Setting v=0v=0 and using G(0)=0G(0)=0 gives G(v∗)≤gv∗=β−G(v∗)G(v_*)\le gv_*=\beta-G(v_*). Thus 0≤G(v∗)≤β/20\le G(v_*)\le\beta/2, and h=1/(1−G(v∗)/β)∈[1,2]h=1/(1-G(v_*)/\beta)\in[1,2]. The supporting line has slope β/(Zh2)\beta/(Zh^2) and zero at a=Z(2h−h2)a=Z(2h-h^2). Combining it with G(v)≥0G(v)\ge0 proves the first assertion. Extend this nonnegative affine bound beyond Λe\Lambda_e and integrate its exponential over [0,∞)[0,\infty). The result is a+Zh2/(qβ)a+Zh^2/(q\beta), which proves the second assertion.

Exact purchase rates for nested clocks

For a common θ∈[0,1)\theta\in[0,1), serve zero-τi\tau_i types immediately and give every other type period

pi(θ)=s2θ+⌈log⁡2τi−θ⌉.p_i(\theta)=s2^{\theta+\lceil\log_2\tau_i-\theta\rceil}.

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 θ\theta. Let pθ(τ)p_\theta(\tau) denote this rounding function for τ>0\tau>0, with pθ(0)=0p_\theta(0)=0. It is nondecreasing in τ\tau. For resource ee define

Pe,θ(v)=∫0vpθ(τe(u)) du,Re(θ)=∫0Λee−Pe,θ(v) dv.P_{e,\theta}(v)=\int_0^v p_\theta(\tau_e(u))\,du,\qquad R_e(\theta)=\int_0^{\Lambda_e}e^{-P_{e,\theta}(v)}\,dv.

Lemma 7.5. The expected number of purchases of resource ee through TT is at most TRe(θ)T R_e(\theta). For every fixed phase and every T≥0T \ge0,

E[ALGT]≤TQ(θ)+KI(θ),\mathbb{E}[\mathrm{ALG}_T] \le TQ(\theta) + K_I(\theta),

where

Q(θ)=12∑iλipi(θ)+∑eweRe(θ),KI(θ)=∑iCi+18∑iλipi(θ)2.Q(\theta)=\frac{1}{2}\sum_i \lambda_i p_i(\theta)+\sum_e w_eR_e(\theta), \qquad K_I(\theta)=\sum_i C_i+\frac{1}{8}\sum_i\lambda_i p_i(\theta)^2.

Proof. Fix a resource and omit its subscript. Let λ0\lambda_0 be its total immediate rate and let p1<⋯<pmp_1<\cdots<p_m be its distinct positive periods, with corresponding group rates γj\gamma_j. Put B0=0B_0=0 and Bj=∑k=1jγkpkB_j=\sum_{k=1}^j\gamma_kp_k. A tick of period pjp_j that is not a tick of pj+1p_{j+1} has exactly groups 1,…,j1,\ldots,j due. For each such group, its pending count comprises its arrivals since its preceding own clock tick, an interval of length pkp_k. The counts of distinct types are independent, so the probability of a nonempty clearing is 1−e−Bj1-e^{-B_j}. These intervals lie in [0,T][0,T] for every positive tick through TT. The nesting of the periods therefore gives the exact expectation

λ0T+∑j=1m(⌊Tpj⌋−⌊Tpj+1⌋)(1−e−Bj)=λ0T+∑j=1m⌊Tpj⌋(e−Bj−1−e−Bj).\lambda_0T+\sum_{j=1}^{m}\left(\left\lfloor\frac{T}{p_j}\right\rfloor-\left\lfloor\frac{T}{p_{j+1}}\right\rfloor\right)(1-e^{-B_j}) =\lambda_0T+\sum_{j=1}^{m}\left\lfloor\frac{T}{p_j}\right\rfloor(e^{-B_{j-1}}-e^{-B_j}).

where the final floor with pm+1p_{m+1} 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

T[λ0+∑j=1me−Bj−1−e−Bjpj]=T∫0Λee−Pe,θ(v) dv.T\left[\lambda_0+\sum_{j=1}^{m}\frac{e^{-B_{j-1}}-e^{-B_j}}{p_j}\right] =T\int_0^{\Lambda_e}e^{-P_{e,\theta}(v)}\,dv.

The last identity follows by integrating over each constant-period rate group; the initial zero-period segment contributes λ0\lambda_0. It also covers m=0m=0.

After TT, each positive-period type has at most one final clearing, costing in total at most ∑iCi\sum_i C_i. Its expected waiting cost is at most λi(Tpi/2+pi2/8)\lambda_i(Tp_i/2+p_i^2/8). Summing proves the claimed finite-horizon inequality, including completion.

Averaging the common logarithmic shift

Lemma 7.6. For uniform θ∈[0,1)\theta\in[0,1),

Eθ[Re(θ)]≤Ze1−1/(2sβℓ)=KrZe,Eθ[Q(θ)]<KL∗.\mathbb{E}_{\theta}[R_e(\theta)]\le\frac{Z_e}{1-1/(2s\beta\ell)}=\frac{K}{r}Z_e,\qquad\mathbb{E}_{\theta}[Q(\theta)]<KL^*.

Proof. For τ>0\tau>0, write pθ(τ)=sτUθ(τ)p_\theta(\tau)=s\tau U_\theta(\tau). For every fixed positive τ\tau, the rounding multiplier Uθ(τ)U_\theta(\tau) has the same distribution as 2U2^U with UU uniform on [0,1)[0,1). The multipliers for different values of τ\tau need not be independent.

Fix vv with Ge(v)>0G_e(v)>0. Use the weights τe(u)/Ge(v)\tau_e(u)/G_e(v) on 0<u<v0<u<v and the convexity of the exponential to obtain

e−Pe,θ(v)≤∫0vτe(u)Ge(v)exp⁡{−sGe(v)Uθ(τe(u))} du.e^{-P_{e,\theta}(v)}\le\int_0^v\frac{\tau_e(u)}{G_e(v)}\exp\{-sG_e(v)U_\theta(\tau_e(u))\}\,du.

Zero-τe(u)\tau_e(u) terms have zero weight and are omitted. Averaging in θ\theta uses only the identical one-dimensional multiplier distributions, yielding

Eθ[e−Pe,θ(v)]≤EU[e−s2UGe(v)].\mathbb{E}_{\theta}[e^{-P_{e,\theta}(v)}]\le\mathbb{E}_{U}[e^{-s2^U G_e(v)}].

If Ge(v)=0G_e(v)=0, then Pe,θ(v)=0P_{e,\theta}(v)=0 and the same inequality is an equality. Tonelli’s theorem and Lemma 7.4, with the same hh for every UU, now give

Eθ[Re(θ)]≤Ze[2h−h2+h2sβEU[2−U]]=Ze[2h−(1−12sβℓ)h2].\mathbb{E}_{\theta}[R_e(\theta)] \le Z_e\left[2h-h^2+\frac{h^2}{s\beta}\mathbb{E}_U[2^{-U}]\right]=Z_e\left[2h-\left(1-\frac{1}{2s\beta\ell}\right)h^2\right].

Here EU[2−U]=1/(2ℓ)\mathbb{E}_U[2^{-U}]=1/(2\ell). Put δ=1/(2sβℓ)=D/(βK)<1\delta=1/(2s\beta\ell)=D/(\beta K)<1. Completing the square gives 2h−(1−δ)h2≤1/(1−δ)2h-(1-\delta)h^2\le1/(1-\delta) for every real hh. As K=r+D/βK=r+D/\beta, this coefficient equals K/rK/r. The mean period is Eθ[pi]=sτi/ℓ\mathbb{E}_{\theta}[p_i]=s\tau_i/\ell, so

Eθ[Q(θ)]≤K∑iyi+Kr∑eweZe<K(∑iyi+∑eweze)=KL∗.\mathbb{E}_{\theta}[Q(\theta)]\le K\sum_i y_i+\frac{K}{r}\sum_e w_eZ_e<K\left(\sum_i y_i+\sum_e w_ez_e\right)=KL^*.

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 Q(θ)<KL∗Q(\theta)<KL^* is certified. At round mm, test the finite grid {j2−m:0≤j<2m}\{j2^{-m}:0\le j<2^m\} at precision 2−m2^{-m}, skipping any candidate whose rounding decisions are unresolved at that precision. This search uses only the instance and the dual scales τi\tau_i. For evaluation, the preceding proof expresses every ReR_e as a finite sum of exponentials; no numerical integration is required.

Lemma 7.7. The phase search terminates and returns Q(θ)<KL∗Q(\theta)<KL^*.

Proof. Lemma 7.6 gives ∫01Q(θ) dθ<KL∗\int_0^1 Q(\theta)\,d\theta<KL^*. The only possible discontinuities are the finitely many rounding breakpoints. Thus some open interval between them has Q(θ)<KL∗Q(\theta)<KL^*, 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 r>1r>1 and β>0\beta>0, the preceding preprocessing and nested-clock policy define a deterministic causal algorithm satisfying

E[ALGT]≤(r+14βln⁡22)L∗T+KI(T≥0).\mathbb{E}[\mathrm{ALG}_T]\le\left(r+\frac{1}{4\beta\ln^2 2}\right)L^*T+K_I\qquad(T\ge0).

If the same LP has a valid finite-horizon lower certificate

E[OPTT]≥κL∗T−BI\mathbb{E}[\mathrm{OPT}_T]\ge\kappa L^*T-B_I

with κ>0\kappa>0 and a fixed finite BI≥0B_I\ge0, then

E[ALGT]≤r+D/βκE[OPTT]+KI+r+D/βκBI.\mathbb{E}[\mathrm{ALG}_T]\le\frac{r+D/\beta}{\kappa}\mathbb{E}[\mathrm{OPT}_T]+K_I+\frac{r+D/\beta}{\kappa}B_I.

In particular its long-run ratio is at most (r+D/β)/κ(r+D/\beta)/\kappa. If the same positive coefficient κ\kappa is valid for all the grids obtained by varying r>1r>1, then for every ε>0\varepsilon>0 a finite grid gives a ratio at most (1+D/β)/κ+ε(1+D/\beta)/\kappa+\varepsilon.

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 L∗>0L^*>0, so it disappears in the long-run ratio. For the final assertion take r=1+κεr=1+\kappa\varepsilon and use the assumed uniformity of κ\kappa across these grids. The boundary constant BIB_I 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 r>1r>1 and β>0\beta>0, the finite preprocessing and nested clocks above define a deterministic causal algorithm such that

E[ALGT]≤rβ+DC(β)E[OPTT]+KI(T≥0).\mathbb{E}[\mathrm{ALG}_T] \le\frac{r\beta+D}{C(\beta)}\mathbb{E}[\mathrm{OPT}_T]+K_I \qquad(T\ge0).

In particular, r=10001/10000r=10001/10000 and β=27/20\beta=27/20 give ratio

CR:=(10001/10000)(27/20)+DC(27/20)<2.110250205.C_R := \frac{(10001/10000)(27/20)+D}{C(27/20)}<2.110250205.

The same guarantee holds for rooted and prescribed-pair aggregation on trees.

Proof. Combine Theorems 7.2 and 7.8. Appendix § 10 certifies C(27/20)>0.886377C(27/20)>0.886377. The positive series ln⁡2>2∑j=039[32j+1(2j+1)]−1\ln2>2\sum_{j=0}^{39}[3^{2j+1}(2j+1)]^{-1} bounds DD from above and gives the strict displayed numerical inequality by rational arithmetic. On a nontrivial instance a positive feasible charge gives L∗>0L^*>0, so the offline lower bound is linear in TT and KIK_I 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 r>1r>1 and β>0\beta>0, and let 0<ε≤10<\varepsilon\le1 be rational. Write BB for the total binary input length, including the encoding of ε\varepsilon. The construction below takes time polynomial in that length and 1/ε1/\varepsilon. The all-free case is served immediately and bypasses the LP.

The LP grid. For a type ii, put Ci=∑e∈RiweC_i=\sum_{e\in R_i}w_e, and let

Γ=∑iλi,λmin⁡=min⁡iλi,M=∑iλiCi.\Gamma=\sum_i\lambda_i,\qquad\lambda_{\min}=\min_i\lambda_i,\qquad M=\sum_i\lambda_i C_i.

The preceding grid contains consecutive powers of rr, starting at the last power at most β/(2Γ)\beta/(2\Gamma) and ending at the first power at least max⁡{2M/λmin⁡,β/λmin⁡}\max\{2M/\lambda_{\min},\beta/\lambda_{\min}\}. For fixed rational r,βr,\beta, the logarithmic magnitudes of these endpoints are polynomial in BB. Thus the number of grid points, the absolute values of their exponents, and their rational encoding lengths are polynomial in BB. 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 L∗L^* be their common value, and set τi=yi/λi\tau_i=y_i/\lambda_i for the selected optimal dual.

In a nontrivial instance, L∗>0L^*>0. Indeed, choose an incidence (i,e)(i,e) and a scale aa. Set cea=wec_{ea}=w_e and

δiea=min⁡{we,a,βweaλi}>0,\delta_{iea}=\min\left\{w_e,a,\frac{\beta w_e}{a\lambda_i}\right\}>0,

with all other variables zero. This is a feasible primal solution of positive rational value. In particular, accuracy proportional to L∗L^* 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 pi≥0p_i \ge0, a zero period means immediate service. At resource ee, sort its users by period and let pe(v)p_e(v) be the resulting rate-quantile function on [0,Λe][0,\Lambda_e], where Λe=∑i:e∈Riλi\Lambda_e = \sum_{i:e \in R_i} \lambda_i. Put

Pe(v)=∫0vpe(u) du,Re(p)=∫0Λee−Pe(v) dv,Q(p)=12∑iλipi+∑eweRe(p).P_e(v) = \int_0^v p_e(u)\,\mathrm{d}u,\qquad R_e(p) = \int_0^{\Lambda_e} e^{-P_e(v)}\,\mathrm{d}v,\qquad Q(p) = \frac{1}{2}\sum_i \lambda_i p_i + \sum_e w_e R_e(p).

The manuscript proves

E[ALGT]≤TQ(p)+∑iCi+18∑iλipi2.(6)\mathbb{E}[\mathrm{ALG}_T] \le TQ(p) + \sum_i C_i + \frac{1}{8}\sum_i \lambda_i p_i^2. \tag*{(6)}

These expressions retain the probability that a scheduled tick is empty.

Lemma 7.10 (Common scaling). For 0<c≤10 < c \le1 and α≥1\alpha\ge1,

Re(cp)≤c−1Re(p),Re(αp)≤Re(p),R_e(cp) \le c^{-1}R_e(p),\qquad R_e(\alpha p) \le R_e(p),

and consequently

Q(cp)≤c−1Q(p),Q(αp)≤αQ(p).Q(cp) \le c^{-1}Q(p),\qquad Q(\alpha p) \le\alpha Q(p).

Proof. The function PeP_e is convex, nonnegative, and zero at the origin. Thus Pe(u)≤cPe(u/c)P_e(u) \le cP_e(u/c) for 0≤u≤cΛe0 \le u \le c\Lambda_e, including when immediate types create an initial flat interval. Substitution gives

cRe(cp)=∫0cΛee−cPe(u/c) du≤∫0cΛee−Pe(u) du≤Re(p).cR_e(cp) = \int_0^{c\Lambda_e} e^{-cP_e(u/c)}\,\mathrm{d}u \le\int_0^{c\Lambda_e} e^{-P_e(u)}\,\mathrm{d}u \le R_e(p).

Increasing every period decreases each exponential integrand. Waiting scales linearly, yielding the two inequalities for QQ.

Write s=2Kln⁡2=2rln⁡2+1/(2βln⁡2)s = 2K \ln2 = 2r \ln2 + 1/(2\beta\ln2) and replace the phase θ∈[0,1)\theta\in[0,1) by a=2θ∈[1,2)a = 2^\theta\in[1,2). For τi>0\tau_i > 0, define

ki(a)=min⁡{k∈Z:a2k≥τi},pi(a)=sa2ki(a).k_i(a) = \min\{k \in\mathbb{Z}: a2^k \ge\tau_i\},\qquad p_i(a) = sa2^{k_i(a)}.

For τi=0\tau_i = 0, set pi(a)=0p_i(a) = 0. Each positive type has exactly one possible breakpoint in this interval, namely the rational mantissa

bi=τi/2⌊log⁡2τi⌋∈[1,2).b_i = \tau_i/2^{\lfloor\log_2 \tau_i \rfloor} \in[1,2).

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 δ=ε/4\delta= \varepsilon/4 and form

H={1+jδ:j∈Z≥0, 1+jδ<2}∪{bi:τi>0}.\mathcal{H} = \{1 + j\delta: j \in\mathbb{Z}_{\ge0},\ 1 + j\delta< 2\} \cup\{b_i : \tau_i > 0\}.

There are O(∣I∣+1/ε)O(|I| + 1/\varepsilon) candidates, all of polynomial encoding length. For any a∗∈[1,2)a_* \in[1,2), take its largest predecessor a∈Ha \in\mathcal{H}. If a=a∗a = a_* there is nothing to prove. Otherwise there is no breakpoint in (a,a∗](a,a_*], so all exponents agree and

p(a)=cp(a∗),c=aa∗≥11+δ.p(a) = cp(a_*),\qquad c = \frac{a}{a_*} \ge\frac{1}{1+\delta}.

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

Q(p(a))≤(1+δ)Q(p(a∗)).(7)Q(p(a)) \le(1+\delta)Q(p(a_*)). \tag*{(7)}

Lemma 7.6 supplies some a∗a_* with Q(p(a∗))≤KL∗Q(p(a_*)) \le KL^*. 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 sˉ\bar{s} with s≤sˉ≤(1+δ)ss \le\bar{s} \le(1+\delta)s. For example, rational bounds l≤ln⁡2≤ul \le\ln2 \le u give

2rl+12βu≤s≤2ru+12βl.2rl+\frac{1}{2\beta u}\le s\le2ru+\frac{1}{2\beta l}.

The positive series

ln⁡2=2∑j≥01(2j+1)32j+1\ln2=2\sum_{j\ge0}\frac{1}{(2j+1)3^{2j+1}}

has tail at most (3/4)9−N(3/4)9^{-N} after NN terms. Refine these rational bounds until their induced upper and lower bounds for ss have ratio at most 1+δ1+\delta, and use the upper bound as sˉ\bar{s}. For fixed r,βr,\beta, this takes O(log⁡(1/δ))O(\log(1/\delta)) terms.

At each candidate use pˉi(a)=sˉa2ki(a)\bar{p}_i(a)=\bar{s}a^{2^{k_i(a)}}, with zero for immediate types. All periods are rational and nested. By common scaling and (7), some candidate satisfies

Q(pˉ(a))≤(1+δ)2KL∗.Q(\bar{p}(a))\le(1+\delta)^2KL^*.

Compute a certified interval [Q‾a,Q‾a][\underline{Q}_a,\overline{Q}_a] of width at most δL∗\delta L^* for each candidate, and choose the smallest upper endpoint. The chosen periods satisfy

Q(pˉ)≤(1+δ)2KL∗+δL∗≤[(1+δ)2+δ]KL∗≤(1+ε)KL∗,Q(\bar{p})\le(1+\delta)^2KL^*+\delta L^* \le[(1+\delta)^2+\delta]KL^* \le(1+\varepsilon)KL^*,

because K>1K>1 and 3δ+δ2≤ε3\delta+\delta^2\le\varepsilon for 0<ε≤10<\varepsilon\le1.

To verify the evaluation complexity, group equal positive periods at each resource as p1<⋯<php_1<\cdots<p_h, with group rates γj\gamma_j, and put Bj=∑k≤jγkpkB_j=\sum_{k\le j}\gamma_kp_k, B0=0B_0=0. Then

Re=λ0,e+∑j=1he−Bj−1−e−Bjpj.R_e=\lambda_{0,e}+\sum_{j=1}^{h}\frac{e^{-B_{j-1}}-e^{-B_j}}{p_j}.

All arguments and coefficients are rational of polynomial encoding length. Their total absolute coefficient size, together with the positive rational L∗L^*, determines a polynomial number of required accuracy bits. Tiny exponential differences need not be evaluated to small relative error.

For a nonnegative rational xx, e−xe^{-x} can be enclosed to absolute error 2−b2^{-b} in polynomial time. If x≥b+1x\ge b+1, use 0≤e−x<2−b−10\le e^{-x}<2^{-b-1}. Otherwise xx 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 E[OPTT]≥[C(β)/β]L∗T\mathbb{E}[\mathrm{OPT}_T]\ge[C(\beta)/\beta]L^*T. 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 r>1r>1, β>0\beta>0 and rational input, deterministic preprocessing polynomial in the input bit length and 1/ε1/\varepsilon produces rational nested clocks satisfying

E[ALGT]≤(1+ε)rβ+DC(β)E[OPTT]+KI′.\mathbb{E}[\mathrm{ALG}_T]\le(1+\varepsilon)\frac{r\beta+D}{C(\beta)}\mathbb{E}[\mathrm{OPT}_T]+K'_I.

Here KI′K'_I includes all completion costs and is independent of TT. With the parameters of Theorem 7.9 and ε=10−3\varepsilon=10^{-3}, the ratio is below 2.113.

Proof. The finite candidate construction gives Q≤(1+ε)KL∗Q\le(1+\varepsilon)KL^*, where K=r+D/βK=r+D/\beta. 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 RvR_v to be the path from a prescribed root to vv 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 rr, β\beta.

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 1/C(1)>1.40820770331/C(1) > 1.4082077033 and CR<2.110250205C_R < 2.110250205 with finite preprocessing. The scalar family attains exactly 1/C(1)1/C(1), 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 C(q)C(q) denote the unrestricted offline cost per unit time for a rate-one Poisson process with setup cost q>0q > 0 and additive waiting. The cluster characterization in § 6.1 also gives

C(q)=lim⁡n→∞E[Dn(q;X1,…,Xn−1)]n,Xj∼iidExp⁡(1),C(q) = \lim_{n \to\infty} \frac{\mathbb{E}[D_n(q; X_1, \ldots, X_{n-1})]}{n}, \qquad X_j \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Exp}(1),

where DnD_n is the exact consecutive-batch dynamic program. Indeed the regenerative clusters have geometric size NN and finite mean cost DD, and both the per-arrival and per-time rates equal E[D]/E[N]\mathbb{E}[D]/\mathbb{E}[N] 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 M≥1M \ge1 and integer gaps in {0,1,…,M}\{0,1,\ldots,M\}. After nn arrivals, a candidate final batch containing jj requests has an excess cost dd above the current optimum DnD_n. Retain only pairs (j,d)(j,d) with 0≤d<M0 \le d < M. A pair is discarded if another has no larger jj and no larger dd. When equal first coordinates occur, keep only the smaller excess. Store the remaining pairs with increasing jj and strictly decreasing dd. At least one retained pair has excess zero.

An excess d≥Md \ge M is never needed again. At the next arrival, starting a singleton costs Dn+MD_n + M, while this old candidate costs at least Dn+dD_n + d 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 j≥Mj \ge M can be replaced by MM. 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 MM 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 kk, the exact marginal cost is

G(s,k)=min⁡{M,min⁡(j,d)∈s(d+jk)}.G(s,k) = \min\left\{M,\min_{(j,d)\in s}(d+jk)\right\}.

Replace each old pair by

(min⁡{M,j+1},d+jk−G(s,k)),\left(\min\{M,j+1\},d+jk-G(s,k)\right),

add the new singleton (1,M−G(s,k))(1,M-G(s,k)), and apply the deletion and merging rules above. Pairs with excess MM are deleted. This gives a deterministic transition s↦T(s,k)s \mapsto T(s,k). The initial state after the first request is s0={(1,0)}s_0=\{(1,0)\}. The stored coordinates lie in {1,…,M}×{0,…,M−1}\{1,\ldots,M\}\times\{0,\ldots,M-1\}, so there are finitely many possible states. Breadth-first search enumerates precisely the states reachable from s0s_0 under the chosen alphabet. No queue-size restriction is imposed on the original instance.

If the gap MM has positive probability, it sends every state to s0s_0. The resulting finite Markov chain therefore has a unique limiting distribution: two copies driven by the same gaps coalesce at their first occurrence of MM. If PP is its stochastic transition matrix and r(s)r(s) its expected one-step marginal cost, the exact long-run cost per arrival is

γ=πr,(8)\gamma= \pi r, \tag*{(8)}

where πP=π\pi P = \pi. This also follows directly by telescoping Dn=M+∑j=1n−1G(sj,kj)D_n = M + \sum_{j=1}^{n-1} G(s_j,k_j) and taking expected Cesaro averages.

Lower and upper quantizations of exponential gaps

In the continuous scalar problem, every gap at least qq can be made an optimal batch boundary. Consequently replacing XX by min⁡{X,q}\min\{X,q\} leaves every finite offline dynamic-programming value unchanged. Let bb be the number of bins, put h=q/bh=q/b, and define

aj=e−jh−e−(j+1)h,βh=1−he−h1−e−h,θh=βh/h.a_j = e^{-jh} - e^{-(j+1)h}, \qquad\beta_h = 1 - \frac{he^{-h}}{1-e^{-h}}, \qquad\theta_h = \beta_h/h.

The conditional mean within bin [jh,(j+1)h][jh,(j+1)h] is jh+βhjh+\beta_h.

For the lower quantization, given a capped gap X=xX=x in [jh,(j+1)h][jh,(j+1)h], set Y=(j+1)hY=(j+1)h with probability (x−jh)/h(x-jh)/h and set Y=jhY=jh with the remaining probability. Use independent rounding coins conditional on the original gaps. Thus E[Y∣X]=X\mathbb{E}[Y\mid X]=X for each original capped gap, not merely after averaging over its bin. For the atom X=qX=q, set Y=qY=q. The resulting probabilities on the grid {0,h,…,bh}\{0,h,\ldots,bh\} are

p‾0=a0(1−θh),\overline{p}_0 = a_0(1-\theta_h),
p‾j=aj−1θh+aj(1−θh)(1≤j<b),\overline{p}_j = a_{j-1}\theta_h + a_j(1-\theta_h) \qquad(1 \le j < b),
p‾b=ab−1θh+e−q.\overline{p}_b = a_{b-1}\theta_h + e^{-q}.

The final term includes the entire atom of the capped gap at qq. The setup cost becomes M=bM=b in units of hh, and the gap alphabet is {0,1,…,b}\{0,1,\ldots,b\}.

For the upper quantization, condition on the bins and replace each finite-bin gap by its midpoint. The exponential density is decreasing, so βh≤h/2\beta_h \le h/2. This follows, for example, by pairing xx and h−xh-x in the integral of (x−h/2)e−x(x-h/2)e^{-x} over [0,h][0,h]. The integer setup cost is now M=2bM=2b in units of h/2h/2. The gap alphabet is {1,3,…,2b−1,2b}\{1,3,\ldots,2b-1,2b\} with probabilities a0,a1,…,ab−1,e−qa_0,a_1,\ldots,a_{b-1},e^{-q}.

The dynamic-programming value DnD_n is the minimum of finitely many affine functions of the gaps. It is jointly concave and is nondecreasing in each gap. For every fixed nn, conditional Jensen therefore gives

E[Dn(lower grid)]≤E[Dn(original gaps)]≤E[Dn(upper grid)].\mathbb{E}[D_n(\text{lower grid})] \le\mathbb{E}[D_n(\text{original gaps})] \le\mathbb{E}[D_n(\text{upper grid})].

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 nn and taking limits gives

γ−(q,b)≤C(q)≤γ+(q,b).\gamma_-(q,b) \le C(q) \le\gamma_+(q,b).

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 PP on the enumerated states and its reward vector rr, put vN=PNrv_N=P^N r. For every integer N≥0N\ge0,

min⁡svN(s)≤πr≤max⁡svN(s),\min_s v_N(s) \le\pi r \le\max_s v_N(s),

because πvN=πr\pi v_N=\pi r. 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 10−1410^{-14}. 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 P≤P‾P \leq\overline{P} and r≤r‾r \leq\overline{r} entrywise, then PNr≤P‾Nr‾P^{N}r \leq\overline{P}^{N}\overline{r}. 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 γ\gamma, and the maximum of its upper iterate is a rigorous upper bound.

All probability enclosures are produced using exact fractions. For 0≤x≤3/20 \leq x \leq3/2, the alternating Taylor tails give

∑j=041(−x)jj!≤e−x≤∑j=040(−x)jj!.\sum_{j=0}^{41} \frac{(-x)^j}{j!} \leq e^{-x} \leq\sum_{j=0}^{40} \frac{(-x)^j}{j!}.

The terms are decreasing in magnitude throughout the relevant tail. The expression 1−hz/(1−z)1-hz/(1-z) is decreasing in zz, which fixes the direction of the conditional-mean bounds. Products involving θh\theta_h and 1−θh1-\theta_h are enclosed separately, so no independence or common extremizer of these interval endpoints is assumed.

Certified values

Both quantizations use b=16b = 16 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.

qqlower bound on C(q)C(q)
7/87/80.6407995521894
10.709707
27/2027/200.886377
189/100189/1001.1245989704271
31.533777646201
62.375717698470
103.218954343659

Table 2.

The midpoint upper graph gives M16<0.7102999314262M_{16} < 0.7102999314262 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 C(27/20)>0.886377C(27/20) > 0.886377 and the positive rational lower series for ln⁡2\ln2 gives CR<2.110250205C_R < 2.110250205.

Conditional gap means and short clusters

We now use the conditional means inside the midpoint bins to improve the offline upper certificate. Let C(q)C(q) be the long-run offline cost per unit time of rate-one Poisson requests, unit additive delay, and a setup cost q>0q > 0. For nn consecutive requests, write Dn(q;x)D_n(q; x) for their optimal completion cost when their n−1n-1 interarrival gaps are xx. As proved in the scalar analysis, an optimum consists of consecutive batches served at their last arrival. Thus DnD_n is the minimum of finitely many affine functions of the gap vector, and is concave and coordinatewise nondecreasing in that vector. Also lim⁡n→∞E[Dn(q;X)]/n=C(q)\lim_{n \to\infty} \mathbb{E}[D_n(q; X)]/n = C(q) for independent rate-one exponential gaps XX.

A finite-input correction of midpoint rounding

Fix m≥1m \ge1, put h=1/mh = 1/m, and cap gaps at one. On each interval [jh,(j+1)h)[jh, (j+1)h), 0≤j<m0 \le j < m, round a gap to its midpoint (j+1/2)h(j+1/2)h; map every gap at least one to one. Denote the resulting random gap vector by YY. Throughout this section the distribution of YY is fixed using this setup-one grid, even when Dn(q;Y)D_n(q;Y) is evaluated at a setup cost q<1q < 1.

Conditional on an internal bin, the mean of an exponential gap is

jh+1−heh−1=(j+1/2)h−δ,δ=h2−1+heh−1>0.jh + 1 - \frac{h}{e^h-1} = (j+1/2)h - \delta,\qquad\delta= \frac{h}{2} - 1 + \frac{h}{e^h-1} > 0.

Let Y‾\overline{Y} be Y−δY-\delta in each internal bin and one on the capped tail bin. For every 0<q≤10 < q \le1, capping a gap at one does not change the optimum: an optimal schedule may cut at every gap at least qq. Conditional Jensen and monotonicity therefore give

E[Dn(q;X)]≤E[Dn(q;Y‾)]≤E[Dn(q;Y)].\mathbb{E}[D_n(q;X)] \le\mathbb{E}[D_n(q;\overline{Y})] \le\mathbb{E}[D_n(q;Y)].

Lemma A.1 (Mean correction using a second setup price). Fix 0<q<10 < q < 1, and put

An=E[Dn(1;Y)],Fn(q)=E[Dn(q;X)].A_n = \mathbb{E}[D_n(1;Y)],\qquad F_n(q) = \mathbb{E}[D_n(q;X)].

Then

Fn(1)≤An−δ[n−An−Fn(q)1−q].F_n(1) \le A_n - \delta\left[n-\frac{A_n-F_n(q)}{1-q}\right].

Proof. For each midpoint gap vector YY, choose an optimal setup-one partition with KnK_n 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 YY by Y‾\overline{Y} reduces the delay of this partition by δ\delta times the number of requests preceding each uncut gap within its batch. There are n−Knn-K_n uncut gaps, each with coefficient at least one. Hence

Dn(1;Y‾)≤Dn(1;Y)−δ(n−Kn).D_n(1;\overline{Y}) \le D_n(1;Y)-\delta(n-K_n).

The same partition, evaluated at setup price qq, also gives

Dn(q;Y)≤Dn(1;Y)−(1−q)Kn,Kn≤Dn(1;Y)−Dn(q;Y)1−q.D_n(q;Y) \le D_n(1;Y)-(1-q)K_n,\qquad K_n \le\frac{D_n(1;Y)-D_n(q;Y)}{1-q}.

These two inequalities use the same fixed midpoint gap vector. Take expectations, use conditional Jensen for the setup-one cost, and use E[Dn(q;Y)]≥Fn(q)\mathbb{E}[D_n(q;Y)] \ge F_n(q). The displayed claim follows.

Let Mm=lim⁡n→∞An/nM_m=\lim_{n\to\infty} A_n/n 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

C(1)≤Mm−δ[1−Mm−C(q)1−q].C(1) \le M_m-\delta\left[1-\frac{M_m-C(q)}{1-q}\right].

No derivative of CC, interchange of perturbation limits, or numerical mixing-time estimate is used here. If Mm≤UM_m \le U and C(q)≥LC(q) \ge L, this implies

C(1)≤U−δη,η=1−U−L1−q.C(1) \le U-\delta\eta,\qquad\eta=1-\frac{U-L}{1-q}.

When η>0\eta> 0, a certified lower bound on δ\delta suffices for a strict upper certificate on C(1)C(1).

An additional nonnegative charge from short clusters

The exact coefficient of the gap shift for a partition with batch sizes ℓ1,…,ℓK\ell_1,\ldots,\ell_K is

W=∑jℓj(ℓj−1)2=(n−K)+∑j(ℓj−1)(ℓj−2)2.W=\sum_j \frac{\ell_j(\ell_j-1)}{2}=(n-K)+\sum_j \frac{(\ell_j-1)(\ell_j-2)}{2}.

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

E=∑j(ℓj−1)(ℓj−2)/2.E=\sum_j(\ell_j-1)(\ell_j-2)/2.

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 KK. Write p=e−1p=e^{-1} and pj=e−jh−e−(j+1)hp_j=e^{-jh}-e^{-(j+1)h} for 0≤j<m0\leq j<m. For a cluster of size ss, let Es(j1,…,js−1)E_s(j_1,\ldots,j_{s-1}) be the largest value of EE among optimal partitions with midpoint gaps (ji+1/2)h(j_i+1/2)h. For every fixed cutoff s∗≥3s_*\geq3, define

Γs∗=p2∑s=3s∗∑j1,…,js−1=0m−1Es(j1,…,js−1)∏i=1s−1pji.\Gamma_{s_*}=p^2\sum_{s=3}^{s_*}\sum_{j_1,\ldots,j_{s-1}=0}^{m-1}E_s(j_1,\ldots,j_{s-1})\prod_{i=1}^{s-1}p_{j_i}.

The two factors pp impose the preceding and following cluster boundaries. Thus Γs∗\Gamma_{s_*} is the expected retained extra charge per arrival in a stationary sequence of gaps. More explicitly, in an input of nn requests, each fixed size s≤s∗s\leq s_* has (n−s−1)+(n-s-1)_+ possible cluster starts whose two boundary gaps are inside the input. Linearity of expectation gives a total expected extra charge at least (n−s∗−1)+Γs∗(n-s_*-1)_+\Gamma_{s_*}. Clusters larger than s∗s_* 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 n→∞n\to\infty proves

C(1)≤Mm−δ[1−Mm−C(q)1−q+Γs∗].C(1)\leq M_m-\delta\left[1-\frac{M_m-C(q)}{1-q}+\Gamma_{s_*}\right].

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 δW\delta W. It completes every finite input.

A reproducible rational certificate

Use m=16m=16 and q=7/8q=7/8. The midpoint graph has 18,666 states and gives the outward-rounded upper bound

U=0.7102999314262.U=0.7102999314262.

The endpoint-rounding lower graph has 59,666 states. Evaluating that same graph with the exponential-bin probabilities for setup q=7/8q=7/8 gives the conservative lower bound

L=0.6407995521894.L=0.6407995521894.

This lower certificate uses its own grid with spacing q/16q/16. That grid is used only to bound the continuous quantity C(q)C(q); it is not identified with the fixed setup-one midpoint distribution in the finite-input lemma. For a completely rational bound on δ\delta, put h=1/16h = 1/16 and

E+=∑j=020hjj!+h2121!11−h/22.E_{+} = \sum_{j=0}^{20} \frac{h^{j}}{j!} + \frac{h^{21}}{21!}\frac{1}{1-h/22}.

The positive exponential series gives eh<E+e^{h} < E_{+}, so

δ>δ−:=h2−1+hE+−1.\delta> \delta_{-} := \frac{h}{2} - 1 + \frac{h}{E_{+}-1}.

All quantities in the following comparison are rational:

η=1−8(U−L)=0.4439969661056>0,C(1)<U−δ−η<0.710155410573,\eta= 1 - 8(U-L) = 0.4439969661056 > 0,\qquad C(1) < U-\delta_{-}\eta< 0.710155410573,

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

Γ6>Γ0:=0.101052891414.\Gamma_{6} > \Gamma_{0} := 0.101052891414.

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, …\ldots, 31, so all dynamic-programming comparisons and tie decisions are exact. Each exponential-bin probability and pp 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

C(1)<U−δ−(η+Γ0)<0.710122517893,C(1) < U-\delta_{-}(\eta+\Gamma_{0}) < 0.710122517893,

and

1U−δ−(η+Γ0)>1.4082077033.\frac{1}{U-\delta_{-}(\eta+\Gamma_{0})} > 1.4082077033.

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

Paper details

vlnc:W_eaggc7d8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI’s Astra, Codex

View statement
Looking for related papers…
Contents