WorksComputer Science
List Update with Per-Page Maximum Delay
Abstract
We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum waiting penalty. Each service can change the permutation and therefore the cost of later accesses. We give a strictly -competitive deterministic algorithm: serve a page when the oldest waiting time reaches two thirds of its current rank, then move it to the front. Our main tool is an asynchronous marked-rank coupling that compares different list orders and different service histories. A temporal transfer principle separates this permutation argument from two waiting-cost inequalities. It gives factor for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor . Two structural conditions on request-specific penalties give factor . In particular, nonincreasing request severity retains factor even with unbounded weight ratios. For linear delay, offline optimization is NP-complete but fixed-parameter tractable in the number of pages. We characterize fixed-list batching, show an gap between the best static order and dynamic reordering, and prove that the optimal deterministic factor for one page is exactly . Counterexamples delineate the threshold rule's scope.
Introduction
A list provides a simple way to store objects that are accessed repeatedly. Finding an object near the front is inexpensive, while finding an object near the end requires a longer scan. Moving accessed objects forward can reduce later search costs. Classical list update studies this reordering decision when each request must be served in sequence. Move-to-front already gives a constant competitive guarantee in that setting [11].
When service may be postponed, reordering is only part of the decision. Several requests for one page can be cleared by a single access. Waiting can avoid repeated searches, but it also leaves an outstanding obligation. Under a request-additive objective, each new request adds its own waiting cost. We consider a different measure: an access pays the maximum waiting time among the requests it clears. Younger requests for the same page share its current waiting charge. Requests for different pages require different accesses and pay separate charges.
We call this problem list update with per-page maximum delay. The algorithm decides when to access each pending page and how to change the list. Accessing a page costs its current rank, counted from one, plus the age of its oldest pending request. The page may then move toward the front for free. Paid adjacent exchanges cost one and are permitted at any time. We compare with an offline optimum that knows the complete timed input and may choose all service times and list operations.
The persistent list makes the timing decision consequential. Serving a page and moving it forward can make another pending page more expensive to access. Conversely, a page that the online algorithm keeps waiting may already have been served cheaply by the offline optimum. Its waiting cannot then be charged to simultaneous offline delay. A successful analysis must account for both different list orders and different sets of completed requests.
Our contributions
Our results concern one access per page, where repeated requests to that page share both the access and the per-batch maximum-delay charge. Classical list update has a changing permutation but no scheduling, whereas maximum-delay aggregation with fixed service costs has scheduling but no persistent list state.
A constant guarantee from asynchronous coupling. We give a simple, deterministic, strictly 5-competitive algorithm, independently of the list length and against an unrestricted clairvoyant comparator. The key is a marked-rank inequality for any completing move-to-front (MTF) service schedule. A temporal transfer proposition then turns this spatial comparison into a competitive guarantee.
Delay and deadline extensions. The same proof interface gives factor 5 for page-specific superadditive waiting penalties, common calendar rates, and additional hard deadlines. Deadlines without waiting penalties admit factor 3. Two distinct conditions on request-specific penalties yield : a bounded superadditive page baseline, or pointwise domination of later requests by times every earlier request on the same page. The latter allows arbitrarily large weight ratios when severity is nonincreasing, with factor 5.
Offline structure and sharp boundaries. For linear waiting, exact offline optimization is NP-complete but fixed-parameter tractable in the number of pages. We characterize fixed-list batching and show that even the best freely chosen static order can lose against a dynamic schedule. For one page the optimal deterministic competitive ratio is exactly 2. The proposed multi-page threshold rule has a lower-bound family approaching , and counterexamples explain where its delay assumptions matter.
Our techniques: separating order from time
Why ordinary inversions are not enough. The classic MTF inversion potential measures disagreement between two permutations. Here the schedules may also disagree about which requests have already been served. In particular, the comparator may have cleared a request while it is still pending online; charging all subsequent online waiting to simultaneous offline waiting would fail. We mark such an online page episode when the comparator serves its oldest request and retain the mark until the online access. For the online and comparator permutations and , use
The extra credit is the offline rank, not merely one token per marked page. An MTF access crosses the pages before its target; the rank-dependent credit is exactly what makes these pairwise inversion changes affordable. Checking accesses and paid exchanges yields the purely spatial inequality
where sums the access ranks of online episodes that are still unmarked when served. No waiting rule is used in this comparison.
Why the remaining accesses can be charged to time. If an online episode ends unmarked, its oldest request has remained pending for the comparator throughout that episode. For each page, these online intervals are disjoint and lie inside comparator pending intervals. A rank-aware threshold therefore supplies and whenever the delay model supports this interval charge. The temporal transfer principle (Proposition 4.1) combines these conditions with (2), yielding a strict factor at . Ordinary linear delay has , hence factor 5.
Why the extensions share one proof. A hard deadline can force an earlier service, but that service is already marked because the comparator must meet the same deadline. For nonlinear or heterogeneous penalties, the permutation argument stays fixed; only the justification of the unmarked-interval charge changes. Superadditivity, a common calendar rate, a bounded page baseline, or domination by an earlier request’s function each supplies a different way to pay for those intervals. The same separation also makes the scope of the theorem transparent: shared-prefix scans or set-valued requests would need a different spatial comparison.
Why the offline state compresses. Under linear per-page delay, holding cost is the number of pending pages. After charging elapsed waiting, an offline dynamic program needs only the current permutation and pending-page set; widely spaced arrivals recover the hardness of classical offline list update.
What the guarantees compare
Let be the number of pages and the number of request occurrences. All online bounds compare complete costs on each finite input; they have no additive term. The exact offline state space has size , so its dependence on input length is polynomial but its dependence on is not. Table 1 separates these guarantees from bounds on a particular online rule.
| Setting | Result |
| Linear waiting, online | Deterministic strict factor 5; the chosen threshold rule has a lower bound approaching 10/3. |
| Page-wise superadditive penalties | Strict factor 5; includes convex waiting and common exogenous calendar rates. |
| Hybrid with deadlines | Strict factor 5 for common page penalties; strict factor for request-specific penalties within a known factor of a superadditive page baseline. |
| Arrival-ordered penalties | Strict factor under one-sided function domination; factor 5 when request severity is nonincreasing, even without bounded weight ratios. |
| Hard deadlines only | Strict factor 3 with one access per pending page. |
| Linear waiting, offline | NP-complete decision problem; exact arithmetic-operation algorithm, ; polynomial-time 5-approximation. |
| One page, linear waiting | Optimal deterministic factor exactly 2; the lower bound applies even allowing an additive constant. |
| Fixed list | Explicit optimal batching in linear time after requests are grouped by page. |
| Best free static order | Polynomial-time assignment formulation, but loss against the dynamic optimum is possible. |
Table 1. The algorithm-specific lower bound does not apply to every online algorithm. The nonlinear theorem does not imply the stated offline state compression beyond linear waiting.
Related work and model distinctions
Classical list update and movement rules. The classical list-update problem serves each requested item immediately, charging its current position and the cost of rearranging the list. Move-to-front is 2-competitive in the standard model, which allows a requested item to move toward the front for free after an access [11]; randomized list-update rules can further improve the competitive ratio [1]. Offline list update is NP-hard [2], and this hardness carries over to our model by spacing requests sufficiently far apart. Recent work by Basiak, Bienkowski, Böhm, Chrobak, Jež, Sgall, and Tatarczuk gives a 3.3904-competitive algorithm for list update with uniform costs, where every adjacent exchange must be paid for [5]. This differs from the standard free-forward model used here. In particular, its numerical competitive ratio is not a bound for our delayed problem, and the values should not be directly compared.
Set-valued requests and dynamic rankings. Online min-sum set cover (MSSC) generalizes instantaneous list update: each request specifies a set of acceptable items, and its access cost is the rank of the earliest item of in the maintained permutation. Fotakis, Kavouras, Koumoutsos, Skoulakis, and Vardas initiated the competitive study of this online problem, including comparisons with static and dynamic permutations [8]. For sets of size at most , Bienkowski and Mucha obtained a randomized -competitive algorithm against the dynamic optimum, as well as an existential deterministic guarantee [7]. Basiak, Bienkowski, and Tatarczuk subsequently gave a constructive deterministic -competitive algorithm against the dynamic optimum [6]. These results are closely related through the persistent permutation and the dynamic benchmark, but their requests are served upon arrival and may be satisfied by different chosen items in the online and offline schedules. Our requests instead name a unique page, and the new decision is when to clear its pending requests. Thus MSSC generalizes the spatial request type of classical list update, not the delayed batching model studied here.
List update with time windows and additive delays. The closest prior work on delaying list accesses is by Azar, Lewkowicz, and Vainstein [4]. They study time windows and request-additive delay functions, obtaining constant competitive algorithms; the published results include factors 24 for time windows and 336 for general delays. Their service operation can scan a prefix of the list once, satisfying requests for several different pages at the cost of the farthest position reached. Our operation accesses one page, clears all requests currently pending for that page, and charges one maximum delay for that page’s oldest pending request. Distinct pages pay separate access and delay charges, even when served at the same instant. Replacing one prefix scan by a sequence of per-page accesses may change a spatial cost of into , while replacing request-additive penalties by a per-page maximum changes the temporal accounting. Neither algorithmic guarantee therefore directly transfers between the two models, nor does a comparison of their constants alone indicate an improvement.
Predictions and maximum-delay service systems. A different information-based variant, list update with predictions, was studied by Azar, Lewkowicz, and Suriyanarayana [3]; it addresses accuracy–robustness tradeoffs for predicted accesses rather than waiting and batching. On the temporal side, maximum-delay aggregation under fixed service costs has constant-competitive algorithms [10, 9]. Those service systems do not retain a changing list permutation after each action. Our marked-rank comparison addresses the additional difficulty that online and offline schedules may have both different list orders and different sets of requests already served. The resulting coupling is specific to per-page episodes; extending it to prefix-wide or set-valued services would require additional accounting for shared access costs or for requests served through different elements.
Organization. The first part develops the model, algorithm, asynchronous comparison, offline structure, and the common principle behind the extensions. Complete event proofs, offline recurrences, reductions, and lower-bound constructions follow in § 8–§ 11.
The Model and Its Waiting Cost
An input consists of a finite sequence of requests , where is one of pages and is its arrival time. Requests with the same arrival time are revealed together, before any actions at that time. The initial permutation is specified and shared by the algorithm and comparator. The final permutation is unrestricted.
Access and rearrangement. At any time a schedule may access a page with pending requests. If its current rank is , the access costs and clears every pending request for that page. The schedule may immediately move that page to any earlier position for free, including leaving it where it is. Other changes are implemented by adjacent exchanges at unit cost. These exchanges may be performed proactively. Operations take no time; simultaneous accesses are ordered, and their ranks are evaluated in that order.
Passing other pages while locating the target does not serve their requests. Thus requests to one page can share an access, whereas requests to different pages cannot share one prefix scan’s cost.
Pending episodes. When a request arrives at a page with no pending request, it starts an episode. Write for this first arrival. Further requests to the page join the episode without changing . If the next access occurs at , the episode contributes delay . Thus a schedule has total cost
The algorithm must eventually clear every request on every finite input, without being told that no more requests will arrive. Its cost includes all accesses and waiting after the final arrival.
Proposition 2.1 (One clock per pending page). If is the set of pending pages in a schedule, then
Each page contributes one while an episode is active and zero otherwise. Integrating gives exactly its episode lengths. This identity is both an online accounting rule and the reason that the offline dynamic program can forget ages after charging past waiting.
Two distinctions in the objective. If ten requests arrive at one pending page, its holding rate is still one. If ten different pages are pending, the rate is ten. Consequently, the objective is neither the sum of individual request delays nor one maximum taken over the entire execution. Even when several pages are accessed at the same time, each page pays its own access and episode delay. We do not combine their ranks or waiting costs into one pooled service charge.
Benchmarks and computation. The offline optimum may use every permitted list operation and choose service times with full knowledge of the input. A strict factor means for every finite timed input . We use rational arrival times for bit-complexity and decision statements. For general continuous penalty functions, the online guarantee is stated with access to their current values and first threshold-hitting times; it does not assert polynomial bit complexity for arbitrary function representations.
Choosing When to Access
The algorithm compares an episode’s age with the cost of accessing its page now. A page near the front should wait less than a page near the end. This comparison must remain current: the algorithm does not freeze the page’s rank when its episode begins.
Fix . The scaled rank-threshold rule accesses a pending page as soon as
then moves to the front. It recomputes all eligibility conditions after every access. Ties may be resolved arbitrarily. The algorithm performs no paid exchanges.
Algorithm 1 Scaled Rank-Threshold MTF
Maintain the list and the oldest arrival of each pending page.
When a request arrives at a nonpending page , set to its arrival time.
Reveal all arrivals at the current time before taking an action.
while some pending page satisfies do
Choose one such page , access it, and clear its pending requests.
Move to the front and remove its episode clock.
Wait for an arrival or the next equality in (5), whichever occurs first.
Why every service hits its threshold exactly. While is pending, another page’s move-to-front can only preserve or increase ’s rank. It cannot suddenly lower the threshold below the current age. Between actions, age increases continuously. Thus every actual access satisfies equality in (5), even when an earlier action at the same time postpones another page’s service. Writing for the sum of access ranks, we obtain
Since ranks never exceed , each episode completes within time units of its first arrival. The rule therefore handles the end of the input through its ordinary timers.
Theorem 3.1 (Scaled threshold guarantee). For every and every feasible comparison schedule with access and paid-exchange cost and delay .
In particular, gives a strict deterministic factor 5.
The two coefficients measure different losses. A larger threshold increases the waiting attached to each access, while a smaller threshold makes it harder to charge early online services to offline waiting. Their maximum is minimized at . The theorem does not assert that this choice or the resulting factor is optimal among all algorithms.
A service can postpone another page's timer
Consider the initial list and . Requests for and arrive at time zero. Another request for arrives at time , and a request for arrives at time one. The second request joins the existing episode; it does not restart its clock or add a second waiting charge.
At time , page has age and rank two, so it is accessed and moved to the front. The list becomes . Page had been due at , but its rank is now two and its threshold moves to . At time two, reaches its rank-three threshold. Moving it forward changes the list to and raises ’s rank again. Page is finally accessed at time three, with age two and rank three.
Figure 1. Filled dots are arrivals; open circles are accesses. An episode’s horizontal length is its single maximum-delay charge. The two arrivals share one episode.
| Access time | Page | Rank | Episode age | List after access |
| 4/3 | 2 | 4/3 | ||
| 2 | 3 | 2 | ||
| 3 | 3 | 2 |
Table 1 (PDF p. 7).
The access total is eight, and delay is , exactly two thirds of that total. A comparator could keep the original list, access at , at zero, and at one, paying in total. Its batches and list movements need not match those of the algorithm. The proof therefore cannot pair service events merely by their chronological order.
The example also explains why an initial-rank timer is a different algorithm. Freezing ’s original rank would serve it at after its access cost had changed. Our rule keeps the exact relation between the cost of a service and the waiting accumulated for it.
Comparing Different Service Times
The main difficulty is the part of online waiting that takes place after the comparator has already served the same request. We distinguish this case explicitly rather than charging every online clock to an offline clock running at the same time.
Which episodes can pay directly to offline waiting?
During an online episode for page , mark that page when the comparison schedule first serves the episode’s oldest request. The mark remains until the online algorithm accesses . Later arrivals to do not change the identity of that oldest request, and do not remove the mark. These marks are used only in the proof; the online algorithm never sees the comparator.
Suppose an online episode ends while its page is still unmarked. Its oldest request has been pending offline throughout that episode. The whole online interval can therefore be placed inside one offline pending interval of the same page. Distinct online episodes for a page have disjoint interiors. If is the sum of access ranks over these unmarked services, threshold equality gives
This charge does not count requests separately. An offline episode may contain many online episodes, but the sum of their lengths is at most the offline interval’s length.

Figure 2. For a fixed page, unmarked online intervals can be charged to offline pending time without overlap. Marks are needed for the other online intervals, which may continue after offline service.
What must be remembered after offline service?
If the comparator serves a request early, its online episode may still be expensive because the online page is far back in the list. The comparison keeps credit for this event at the page’s offline rank. That credit changes when the comparator rearranges its list and is released when the online algorithm finally clears the episode.
The rank is important. The number of marked pages alone does not record how many pairwise order differences must be removed by a later move-to-front. The offline rank supplies precisely the quantity that appears in the inversion calculation on the next page.
One potential for order and unfinished episodes
Let count unordered page pairs whose relative order differs in the two lists. If is the set of marked pages, define
It starts at zero and is always nonnegative. Arrivals and waiting do not change it. Only accesses, free forward moves, paid exchanges, and the associated mark changes need to be checked.
An online access removes order disagreements. Suppose the algorithm accesses at rank , while its offline rank is . Let be the number of pages preceding in both lists. Moving to the front changes the inversion count by
For a marked page, clearing its episode also removes from the potential. Since , this decrease pays for the access: . For an unmarked page, no credit is removed, but gives . These are exactly the services already covered by (8).
Offline changes pay for the credit they create. An offline access at rank may create a mark of value . Moving that marked page forward reduces its own rank contribution and increases the ranks of at most the pages it passes. The marked-rank sum cannot increase during this move. At most new inversions are created. If no mark is created, the same crossed pages bound the increase directly. Each paid adjacent exchange changes at most one inversion and two units of marked-rank credit.
| Event | Bound used in the sum |
| Online access, marked page, rank | |
| Online access, unmarked page, rank | |
| Offline access and free forward move, rank | |
| Offline paid adjacent exchange |
Table 2. The four event types behind the marked-rank comparison. Complete case calculations appear in § 8.
Summing and discarding the nonnegative final potential yields the combinatorial comparison
It does not use the threshold rule. What remains is a temporal certificate for the unmarked accesses; the list comparison is reused without change in every extension below.
A transfer from temporal charges to total cost
The next proposition states the reusable interface between the permutation argument and a waiting policy. It does not assume a specific delay function or a threshold-equality identity.
Proposition 4.1 (Temporal transfer). Let be a feasible, completing MTF algorithm that makes no paid exchanges and clears every pending request at its accessed page. Fix a feasible comparator with the same initial list, and let be the sum of ranks of ’s accesses unmarked relative to . Suppose that for some and ,
Then
If these conditions hold on every finite input against every feasible comparator for a fixed and , then is strictly -competitive. For the fixed comparator , instead gives . If there are no waiting penalties and every access is marked on every finite input against every feasible comparator, then is strictly 3-competitive.
The proof in § 8 combines the coupling with (4.4). For linear waiting, both conditions hold with and threshold equality gives . With deadlines, an early deadline-driven access is already marked, so equality for all online services is replaced by ; the unmarked-access charging inequality is still required.
Offline Structure
The online algorithm gives a polynomial-time 5-approximation offline, but exact optimization reveals additional structure. The linear waiting objective permits a finite state description that does not retain the arrival time of each pending episode.
Charge waiting before forgetting its age. Between two consecutive arrival epochs, move every operation to the left endpoint while preserving its order. No request arrives in the open gap, the final permutation and pending set are unchanged, and any episode cleared earlier has smaller delay. An optimum can therefore act only at arrival epochs, including the final completion actions.
At a layer, store : the current permutation and the pending-page set. Across a gap , add . All past waiting is now paid, so the remaining problem does not depend on how long each page has already waited. New arrivals take the union with . Within the layer, paid exchanges change , while an access pays its rank, removes one page from , and permits every free forward destination. Shortest-path closure in this finite graph includes arbitrary orders of same-time actions.
Theorem 5.1 (Offline computation). For linear delay and , the offline optimum can be computed in arithmetic operations and space. With rational input, the decision problem is NP-complete.
For this bound, an access followed by a free forward move is represented by paying for the move before the access and then paying its lower rank; the total is unchanged. The state bound gives fixed-parameter tractability in , rather than an exponent of on the input length. The NP-hardness reduction places classical list-update requests so far apart that optimal waiting cannot cross the next arrival. Membership in NP follows by shortening paid-swap paths inside each arrival layer. § 9 supplies both arguments and the bit-complexity qualifications.
The option not to move matters. In the initial list , let be requested at zero and at time ten. Accessing immediately and leaving it in place, then accessing , costs three. Forcing move-to-front after every offline access changes this instance’s optimum to four. An exact oracle must therefore include all optional forward destinations, not just move-to-front.
A fixed list is simpler, but insufficient. If a page has fixed rank and distinct arrivals , its optimal cost is
Each gap can either remain inside a batch, paying its length, or separate two batches, paying another access. Empty pages contribute zero. If the initial static order may be chosen for free, assigning each page to a distinct rank with cost (5.1) is a minimum-cost matching problem. Nevertheless, even this best static order can be more expensive than a dynamic schedule: long successive phases requesting one page at a time reward moving the currently active page forward. Exact static optimization cannot replace dynamic reordering.
Beyond Linear Waiting
The inversion calculation does not refer to elapsed time. It needs only to distinguish marked from unmarked services. This allows a broader delay theorem whenever the costs of disjoint online waiting intervals can be paid by the offline episode containing them.
For each page , fix a function that is continuous, nondecreasing, unbounded, and zero at zero. All requests of that page use the same function. An episode of duration pays , equivalently the maximum of the individual -penalties of its requests. Assume further that
This includes positive page-specific linear weights and nondecreasing unbounded convex functions vanishing at zero. Different pages may use different functions, such as with .
Theorem 6.1 (Page-specific waiting penalties). Access page when reaches , then move it to the front. Under the preceding assumptions, this algorithm is strictly 5-competitive.
What changes in the proof. Exact threshold equality still gives . For the offline charge, consider unmarked online intervals of lengths inside one offline episode of page , of length . They are disjoint, so . Hence
This replaces the linear interval-length comparison. The list potential, including its treatment of paid exchanges and optional free moves, stays unchanged. Continuity supplies exact first hitting, and unboundedness ensures completion without another request.
A common calendar rate. There is another useful form of the same interval argument. Let page have an exogenous nonnegative rate , and charge an episode the amount . Rates may vary over absolute time but are shared by the two schedules. If they are locally integrable and every tail integral is infinite, the accumulated cost is a continuous clock that eventually reaches any threshold. Costs on disjoint intervals add directly, giving the same factor five. The algorithm needs the current accumulated clock, not future values of the rate.
The scope is per page. The theorem does not allow an arbitrary new waiting function for each request to the same page. In that model the oldest request need not determine the maximum penalty, and the costs of disjoint online episodes need not sum to at most the cost of an offline episode containing them. The counterexamples on the next page make both this distinction and the role of (6.1) explicit. The offline pending-set compression in § 5 is a linear-delay result; past ages cannot in general be forgotten for nonlinear penalties.
Adding hard deadlines and bounded request heterogeneity. The same marked-rank method also tolerates hard deadlines. Mark a page whenever the comparator has served any request in its current online episode. An algorithm access forced by a deadline is then always marked. With a common superadditive penalty function per page, the usual threshold rule combined with the earliest-deadline trigger remains strictly 5-competitive; if only deadlines are charged as hard feasibility constraints, serving at the earliest pending deadline is strictly 3-competitive. More generally, if every request’s penalty lies between a page-specific superadditive baseline and times that baseline, the combined algorithm is strictly -competitive for known . The full statement and proof appear in Theorem 10.5 and Corollary 10.6.
A complementary extension: arrival-order domination. A common page baseline is not the only way to charge heterogeneous requests. Suppose every request has a superadditive penalty function, and a later request for the same page has a function at most times that of any earlier request, pointwise in waiting time. There need not be a fixed page baseline: severity may decrease without bound, and increases need only be controlled relative to earlier requests. An unmarked online episode lies inside one offline episode; its oldest offline request supplies a single superadditive function that dominates the penalties of all the online requests up to factor . The same argument now gives a strict factor. In particular, for the original factor 5 holds even with arbitrarily large decreases in weights. This contrasts with the rapidly increasing weights in the negative example of § 7. The full proof is Theorem 10.7.
Bounds and Limits of the Rule
The factor five is an upper bound for a particular deterministic algorithm. It is useful to separate its limitations from lower bounds that apply to all online algorithms.
A lower bound for the scaled threshold
Start with the list and repeatedly request , separating consecutive requests by . Every online episode finishes before the next arrival. Each requested page is at rank , waits , and costs . After one block the list returns to its initial order. In comparison, keeping the initial list fixed and serving immediately costs per block. Therefore
Repeating blocks absorbs any fixed additive constant. This family approaches for our choice . It approaches four for , whose proved upper bound is six. Neither statement is a lower bound of four on the problem itself.
Two failures beyond the delay assumptions
Concave waiting. For one page with , , a fixed threshold serves after time . Release requests at intervals . The algorithm serves them separately and pays . Offline may batch all of them at the last arrival for
The ratio grows without bound. Concavity makes one long offline episode much cheaper than the sum of the shorter online episodes. The interval charge used by the theorem cannot hold in this case.
Request-specific weights. Even linear functions can violate the required sharing when their weights vary within a page. For fixed , take one page and requests with
and charge each batch the maximum of over its requests. A rule that serves when this maximum reaches clears request before the next one arrives, paying in total. At time one, however, every weighted age is exactly , so a single offline batch costs . The construction is a family of finite inputs; it does not require infinitely many arrivals in finite time. Both examples disprove the corresponding fixed-threshold extension. They do not rule out a constant guarantee for a different algorithm in those models. Complete calculations appear in § 11.
Problem lower bounds and randomization
Already with one page, every deterministic completing algorithm has competitive ratio at least two. A direct adversary releases each next request shortly after the algorithm serves the previous one. The one-page offline formula decides independently whether each arrival gap should be crossed by one batch or split by an extra access. Comparing these costs yields the lower bound, including against a fixed additive constant; § 11 gives the full argument. The matching upper bound is equally simple: when there is only one page, serve each pending episode exactly one unit after its first arrival. A union of length-one intervals beginning at requests is a samplewise offline lower certificate, while these first-arrival intervals are disjoint across online episodes. Thus the best deterministic factor for one page is exactly two (Theorems 11.1 and 11.2). The five-factor multi-page bound and (15) address different statements.
Randomized list update improves on deterministic reordering in the classical problem [1]. Here, a randomized service or reordering decision can change the future sequence of physical accesses. An oblivious timed request sequence therefore does not automatically produce an oblivious access sequence for a classical randomized list algorithm. A transfer must control that dependence or analyze the timing and reordering together.
One simple randomization does not improve the present certificate. Draw a positive global scale independently of the input and run the corresponding deterministic threshold. Averaging Theorem 3.1 gives
Both coefficients could be below five only if and , contradicting . The best uniform factor furnished by this inequality is therefore five, attained by the deterministic scale . This is a limitation of the certificate, not a lower bound on randomized algorithms or on a sharper analysis of random scales.
What the comparison leaves to improve
The main algorithm uses one clock per pending page and one familiar reordering rule. Its analysis isolates two costs: creating marked-rank credit when the comparator acts, and paying unmarked online intervals from offline waiting. Improving only the numerical threshold balances these two losses but does not reduce their combined factor below five. A sharper comparison or a different reordering rule is needed for a better guarantee through this approach.
Offline optimization presents a complementary question. The exact state space separates input length from the number of pages, while the static-order example shows why choosing one permanent order is insufficient. A separate offline approximation could exploit future arrivals while retaining adaptive list positions; an improved online algorithm would also improve the present offline guarantee.
The technical part now establishes every comparison used above. It first proves the event inequalities and threshold analysis, then gives the exact offline construction and complexity reduction, extends the interval charge, and verifies the lower bounds and failure examples.
The online comparison
The proof separates list reordering from the timing rule. We first compare the access costs of a move-to-front schedule and an arbitrary feasible schedule. We then use the threshold rule to charge the remaining accesses to the comparator’s waiting cost. Throughout this section, denotes the algorithm’s list and the comparison list. Their initial permutations are identical. We write and for the current ranks of page , and let include both accesses and paid adjacent exchanges.
A coupling for delayed move-to-front schedules
An episode of starts when a request arrives to a page with no pending requests and ends when next accesses that page. Its oldest request is a particular occurrence in the input, not merely a page identity. Mark a page during its current episode once serves that oldest request. Retain the mark until ends the episode. In particular, later arrivals to a marked page do not remove its mark, even if they become pending in .
For the analysis, reveal all arrivals at a timestamp first, then process the actions of , and finally those of . Actions within each schedule retain their original order. The two permutations are independent, so this interleaving changes neither schedule’s cost or behavior. It only specifies the marks at simultaneous accesses. A new episode starts unmarked because its oldest request has just arrived. Endpoints do not affect any waiting-time integral used below.
Call an access of unmarked if its page is unmarked immediately before that access. Let be the sum of the access ranks at these accesses. This quantity measures access cost, not the number of accesses.
Lemma 8.1 (Move-to-front coupling). Let be any completing schedule that clears a page’s pending requests at each access, moves the accessed page to the front, and makes no paid exchanges. Its timing decisions may be arbitrary. For every feasible comparison schedule with the same initial list,
The comparator may perform proactive paid adjacent exchanges and choose any permitted free forward move after each access.
Proof. Let count unordered pairs of pages whose relative orders differ between the lists. Use the potential
It is nonnegative and initially zero. Arrivals do not change it: an arrival either joins an existing episode without changing its mark or starts an unmarked episode. Passage of time also leaves it unchanged.
Consider an access by to a page of rank , and write . Let be the number of pages preceding in both lists. Among the pages crossed by the move to front, exactly create an inversion and the other remove one. Thus
If is marked, ending its episode removes the term from the potential. The ranks and marks of other pages in do not change, so
If is unmarked, the marked-rank term is unchanged and , giving
Consequently all accesses of satisfy
Next consider an access by to a page of rank , including its chosen free forward move. If this access first serves the oldest request of 's current episode for , mark before accounting for its free move. This increases the second term of (17) by . A forward move through positions increases the inversion count by at most . When is marked, its rank decreases by , whereas at most other marked pages increase their ranks by one. Hence the sum of marked ranks cannot increase during that move. The total potential increase is at most .
If was already marked, the same argument applies without the new-mark cost. If remains unmarked, its forward move increases the marked-rank term by at most and the inversion count by at most . Its total increase is again at most . This case also covers comparison accesses that serve no request from a current episode of .
Finally, a paid adjacent exchange by changes the inversion count by at most one. Its change in the marked-rank term is zero when both exchanged pages, or neither, are marked; otherwise its magnitude is two. Each paid exchange therefore increases by at most three. Summing comparison actions gives
Combining (19) and (20), and using the zero initial potential, we obtain
Dropping the nonnegative final potential proves the claim. No condition on the final permutations is needed.
Proof of Proposition 4.1. By Lemma 8.1 and the two temporal bounds,
For , both coefficients equal . If , Lemma 8.1 instead gives for the fixed comparator. Applying the respective bound on every finite input against every feasible comparator proves the competitive guarantees, since is feasible and completing. The initial potential is zero and the final potential nonnegative, so no additive term is needed.
Threshold equality and delay charging
Fix . The scaled rank-threshold algorithm accesses a pending page when its oldest pending age reaches and moves it to the front. After each access it recomputes all thresholds. If several pages are eligible, it may select any one of them.
Lemma 8.2 (Exact threshold and finite completion). Every access of the scaled rank-threshold algorithm occurs at age exactly . Every episode beginning at ends by , where is the number of pages. In particular,
Proof. A new episode starts at age zero and has a positive threshold. Moving any other page to the front leaves ’s rank unchanged or increases it by one; it never decreases that rank. Between discrete events the episode’s age increases continuously. The algorithm acts at the first threshold equality, and an intervening access can only increase another pending page’s threshold. Therefore no pending age exceeds its current threshold, and every actual access has equality. This reasoning also covers ties: serving one eligible page may make another temporarily ineligible, but cannot create an overshoot.
Every rank is at most , so an episode cannot persist beyond age . Each access clears at least one request that is never cleared again, and hence a finite input has only finitely many accesses. This also rules out an infinite same-time action loop. Summing the threshold equalities over all completed episodes gives the two cost identities. □
Lemma 8.3 (Charging unmarked episodes). For the scaled rank-threshold algorithm and every feasible comparator,
Proof. Consider an unmarked algorithm episode for page , beginning at and ending at . Its oldest request has not been served by before the algorithm’s access. Thus is pending in throughout . The interval’s length is exactly times the algorithm’s access rank by Lemma 8.2.
Distinct algorithm episodes for the same page occupy disjoint intervals, apart from endpoints. Their unmarked intervals can therefore be charged without repetition to that page’s pending time in . Since the comparator’s total delay is the integral of its number of pending pages, summing over pages gives the claimed inequality. The argument permits several algorithm episodes to lie inside one longer comparison episode. □
Theorem 8.4 (Scaled rank-threshold guarantee). For every , every finite input, and every feasible comparison schedule ,
Thus its strict competitive factor is at most . Taking gives factor five; taking gives factor six.
Proof. Lemmas 8.2 and 8.3 verify the temporal assumptions of Proposition 4.1 with . That proposition gives (21) and its constants. The empty input has zero cost and satisfies the same statement. □
For linear delay, the rule has a direct event implementation. Its next possible service time is the minimum of over pending pages, unless an arrival occurs earlier. A scan of the list updates ranks and finds this minimum in arithmetic operations per event. There are request arrivals and at most accesses, so chronologically presented input can be processed in arithmetic operations and working memory. For and rational arrival times, all service times and comparisons have polynomial bit complexity. The implementation uses its own timers and does not need to know or the last arrival time.
Offline computation and complexity
This section concerns the linear-delay model. Let be the number of requests and let be the number of pages. Requests are supplied in nondecreasing arrival-time order. Repeated requests at the same time are allowed, and all such requests are revealed before any action at that time. The terminal permutation is unrestricted.
Arrival epochs and a finite-state optimum
Lemma 9.1 (Arrival-layer normal form). Every finite feasible schedule can be replaced, without increasing its cost, by one whose accesses and paid exchanges all occur at request-arrival epochs. At each epoch there are at most useful accesses. The replacement retains the freedom to choose any legal forward position after an access.
Proof. An access to a page with no pending request is unnecessary. If its rank is and its subsequent free move advances it by positions, replace the access and free move by paid adjacent exchanges. This produces the same permutation and pending set and costs . An access followed by no move can simply be deleted. Thus we may assume that every access clears a nonempty pending set.
Consider consecutive distinct arrival epochs . Move all operations in the open interval to immediately after the operations originally performed at , retaining their relative order. There is no intervening arrival, so every access clears the same requests, all intermediate permutations remain the same, and every free or paid move remains legal. Access and exchange costs are unchanged, while every affected request is served weakly earlier. Hence waiting costs do not increase. Paid exchanges before the first arrival may likewise be postponed to that arrival, before the schedule’s original actions. All operations after the last arrival may be moved to that arrival. Applying these transformations gives the claimed normal form.
After a page is accessed at one epoch, it has no pending request and no new request is revealed until the next epoch. Thus there is at most one useful access to each page at an epoch. No part of the argument requires a free move to reach the front: the original forward destination is preserved. □
For a schedule, let be its pending-page set. Its linear waiting cost is
Indeed, each pending episode contributes one to the integrand throughout its duration and contributes exactly that duration to the objective. Consequently, if waiting is charged as time passes, the remaining cost from a given time depends only on the permutation and the pending-page set. The ages of currently pending episodes need not be stored: their past waiting has already been paid.
Theorem 9.2 (Exact parameterized algorithm). Set . The offline optimum can be computed in arithmetic operations, using space. The algorithm permits arbitrary paid adjacent exchanges and all legal free forward moves. For rational arrival times, it is a fixed-parameter tractable exact algorithm with parameter , with polynomial additional dependence on the binary input length.
Proof. First observe that optional free forward moves need not appear explicitly in an optimum. An access at rank followed by a free forward move of positions can instead be implemented by paid forward exchanges before the access and then an access at rank . The total cost is still , the access occurs at the same time, and the final permutation and pending set are identical. All other operations can be retained in their original order. Thus the optimum is unchanged if every forward movement is paid and accesses themselves leave the permutation unchanged.
Construct a directed graph with one vertex for each permutation of the pages and each subset of pages. Its arcs encode instantaneous actions:
An adjacent exchange in has cost one and leaves unchanged.
Accessing has cost , removes from , and leaves the permutation unchanged.
Every vertex has outgoing arcs. A path represents a legal sequence of actions at one time; conversely, the preceding transformation represents every useful instantaneous action sequence by a path of the same cost, including sequences originally using optional free forward moves. All arc costs are positive. One could include all free-forward access arcs explicitly, but they are redundant for shortest-path distances.
Let be the distinct arrival epochs, with , and let be the set of pages requested at . Let be the minimum cost just after the actions at , with waiting already charged through . To pass from epoch to epoch , each state first pays and then activates the new requests. Thus its cost is a candidate seed for state . Take the minimum when several predecessor states give the same seed. Apply multi-source Dijkstra to these seeds to obtain at every vertex. For the first epoch the unique predecessor is the given initial permutation with empty pending set and zero cost, and the first waiting increment is zero. Lemma 9.1 and (22) show inductively that this recurrence represents every normalized feasible schedule and assigns it its exact cost. The answer is
In particular, all requests are completed; no constraint is imposed on the terminal list. Empty input has value zero.
The graph has vertices and arcs. Multi-source Dijkstra with a binary heap costs per epoch, and two cost vectors suffice between epochs. The graph and the two vectors use space. The displayed time bound counts arithmetic operations. For rational timestamps encoded in binary, all relevant costs are sums of integer access costs and integer multiples of differences of input timestamps. They have polynomial encoding length in the input size; exact additions and comparisons therefore add only a polynomial bit-complexity factor. The exponential factor depends only on .
The state compression is specific to linear waiting, or to other delay rules for which the accrued cost has an appropriate memoryless state description. It is not asserted for arbitrary age-dependent episode penalties. In particular, nonlinear penalties in the online extension do not automatically admit the same offline state space.
NP-completeness for an unrestricted number of pages
Theorem 9.3 (Offline decision complexity). Given rational arrival times and a rational bound , deciding whether there is a complete schedule of cost at most is NP-complete.
Proof. For membership in NP, use the arrival-layer normal form. There are at most useful accesses at each epoch. Between consecutive accesses, replace the paid exchanges by a shortest sequence of adjacent swaps producing the same endpoint permutation. Such a sequence has length at most . The same replacement applies before the first and after the last access at the epoch. The resulting certificate has elementary actions. The free forward destination of each access is recorded explicitly. Legality, completion, and the total rational cost can all be checked in polynomial time.
For NP-hardness, reduce from classical offline list update, which is NP-hard [2]. Let its initial list contain pages and its request sequence have length . Put request at time , where . Serving every request immediately without changing the list is feasible and costs at most . If a request were still pending at the next arrival, its page episode would eventually pay waiting cost at least . Such a schedule cannot be optimal. Consequently, an optimum serves each request before the next one arrives.
Apply Lemma 9.1. Each request is now served at its own arrival, with zero waiting, and the same ordering and list operations form a classical list-update schedule. Conversely, any classical schedule can be executed at these arrival epochs with exactly its original cost and zero waiting. The two optimal values are equal, and the construction uses timestamps of polynomial encoding length.
The classical cost convention in this reduction agrees with ours. In the full-cost model an access at rank followed by a free forward move of positions can be replaced by paid swaps before the access, followed by an access at rank , with the same total cost and final permutation. Thus allowing optional free forward moves does not invalidate the classical offline hardness statement. Also, changing classical access cost from to adds exactly to every schedule, so the partial- and full-cost offline hardness statements transfer directly.
Exact fixed-list computation and its limitation
Proposition 9.4 (Fixed permutation). Suppose no list changes are permitted. For a page of fixed rank with distinct arrival times , its optimum cost is zero if and otherwise equals
Summing these quantities over pages gives the fixed-list optimum, which can be computed in time from chronologically ordered input.
Proof. Pages are independent when ranks are fixed. An access clears all pending requests of its page, so its batches consist of consecutive arrivals of that page. Move each access to the last arrival of its batch, reducing waiting without changing the partition. The cost of a batch is plus the sum of the gaps internal to that batch. Starting with one access cost , each consecutive gap independently either remains inside a batch, at the cost of its length, or is cut, at the cost of one additional access . Choosing the cheaper option proves the formula. Equal-time requests can be collapsed, since they are always cleared together.
Proposition 9.5 (Best freely chosen static permutation). If an initial permutation may be chosen at no cost and must then remain fixed, an optimal choice and schedule can be computed in polynomial time.
Proof. Compute from (23) for each page and each possible rank . Assigning pages to distinct ranks is a minimum-cost perfect matching in the bipartite graph of pages and ranks, where edge has cost . The resulting permutation, with the per-page partitions in Proposition 9.4, is optimal. This statement does not include the cost of changing a given initial permutation: adding that permutation’s inversion cost would not be the separable assignment objective used here.
Proposition 9.6 (Static permutations cannot give a constant factor). Even if its initial permutation is chosen for free, the best fixed-list schedule can be a factor approaching more expensive than the unrestricted offline optimum.
Proof. Start the unrestricted schedule in order . For an integer , give consecutive requests to , then to , and so on through . Space all arrivals by , so every consecutive gap of a given page exceeds every possible rank. Each page has requests, and Proposition 9.4 gives cost if it is assigned rank . Thus every freely chosen static permutation costs .
A feasible dynamic schedule serves every request immediately and moves the accessed page to the front. The first access in phase has rank ; the other accesses of that phase have rank one. Its total cost is . Hence the static optimum divided by unrestricted OPT is at least
Letting grow proves the claim. The construction has zero waiting in the displayed dynamic comparison schedule.
Extensions of the delay charge
The list comparison in Lemma 8.1 does not involve waiting costs. Proposition 4.1 requires the temporal bounds and , together with feasibility and completion. Without deadlines, our rules satisfy exact threshold equality at every service. With deadlines, services may occur earlier; only unmarked services need hit their thresholds exactly for the interval charge. We verify these properties for each model below. Every access still clears one page, and both schedules face the same input penalties and deadlines.
Superadditive penalties for elapsed waiting time
For each page , fix a function which is continuous, nondecreasing, and unbounded, with . Assume also that
An episode beginning at and served at incurs penalty . Since the function is nondecreasing and is common to all requests on page , this is the maximum of the requests’ individual penalties in that episode. Functions may differ between pages. The algorithm triggers when first reaches .
Lemma 10.1 (Superadditive interval charge). Under these assumptions, every algorithm access occurs with penalty , every finite input is completed, and
Here is the sum of the comparator’s episode penalties.
Proof. Continuity gives equality at the first threshold crossing. As in Lemma 8.2, other move-to-front operations only increase a pending page’s rank, so they cannot cause a penalty to overshoot its threshold. This also applies when has flat portions. Since is unbounded, an episode ends no later than the first age at which reaches . The number of accesses remains at most the number of requests, so completion is finite.
Every unmarked algorithm episode lies within a single comparison episode of the same page: its oldest request is pending throughout its interval in the comparator. Group the unmarked intervals by their containing comparison episode. If their lengths are and that comparison episode has length , the intervals are disjoint and . Superadditivity and monotonicity imply
Each term on the left is times its algorithm access rank. Summing these inequalities over comparison episodes proves .
Theorem 10.2 (Superadditive episode penalties). For the functions above, scaled rank-threshold MTF satisfies
against every feasible comparator. In particular, gives a strict competitive factor of five.
Proof. The marked-rank coupling gives . By Lemma 10.1, , and exact threshold equality gives . Combining these facts proves the result.
Continuous nondecreasing unbounded convex functions with value zero at zero satisfy (24). Indeed, for , convexity gives and the corresponding inequality for ; adding proves superadditivity. Positive page-specific linear weights are a special case. The theorem does not require strict increase or strict convexity.
The interval inequality is substantive: Proposition 11.4 shows that the fixed-scale rule has unbounded ratio on concave powers, already for one page. That statement concerns this rule, not every possible algorithm for those penalties.
Exogenous rates on the time line
For each page , let be an exogenous locally integrable rate, shared by the two schedules. An episode has penalty
Nonnegativity makes this the maximum of the integrals from the individual request arrival times to , since the oldest arrival gives the largest integration interval. Rates may vary over time and need not be known in advance. The algorithm observes the penalty accrued by each pending page and acts when it first reaches . To ensure completion of every finite input, assume
Local integrability makes every accrued-penalty function continuous. Condition (26) permits intervals of zero rate but rules out a pending page whose remaining lifetime penalty is bounded.
Lemma 10.3 (Charging common calendar rates). For the rate model, the algorithm completes every finite input and satisfies and .
Proof. Continuity and nondecreasing accrued penalties give exact threshold equality, because other move-to-front operations cannot lower a pending page’s threshold. Condition (26) ensures that an episode starting at reaches penalty in finite time, so it must be served by then. Summing equality at service gives .
As before, each unmarked algorithm episode occupies an interval during which the same page is pending in . These intervals are disjoint for each page. Since the rate is nonnegative and common to the two schedules, their penalties sum to at most that page’s total pending-rate integral in . Equivalently,
The equality on the right follows by summing the integrals of the comparator’s disjoint episodes for each page.
Theorem 10.4 (Common exogenous page rates). Under (25)–(26), the scaled rank-threshold algorithm satisfies
In particular, gives a strict factor of five without knowledge of future rates.
Proof. Apply Lemma 8.1 and Lemma 10.3, then use .
The rule uses only presently accrued penalties. Its continuous-time description assumes access to their first hitting times; the number of accesses is still at most . For arbitrary functions or rates, this is not a claim of polynomial bit complexity for evaluating those hitting times. The rates must be external to the two schedules: replacing a common calendar rate by a rate reset or changed separately by each algorithm’s actions would invalidate the interval comparison. Likewise, the elapsed-time theorem uses one fixed function per page, rather than arbitrary functions for different occurrences of that page.
Hard deadlines and bounded request heterogeneity
We next allow both hard deadlines and some heterogeneity among the penalties of requests for the same page. The result is not a consequence of applying the previous page-specific theorem independently to each request: a single page access must clear all of them, and the maximum penalty need not belong to the oldest request.
For each request , let be its page, its arrival, its deadline, and its waiting penalty. A page access at time clears all requests then pending at that page and incurs the penalty over those requests. Every request must be served no later than its finite deadline. Infinite deadlines simply mean that the request has no hard deadline. An online algorithm learns and when request arrives.
Fix a known . For each page , assume there is a continuous, nondecreasing, unbounded, superadditive function , with , such that every request for satisfies
All are assumed continuous, nondecreasing, and zero at zero. The functions need not be identical within a page.
For a pending page write and let be the earliest deadline among its pending requests. Fix . Serve at the first time that either or , then move to the front. Recompute eligibility after each access. At a common timestamp, reveal arrivals first and repeatedly clear every page that is eligible by either condition; all pending deadlines must be met.
Why no new marks are necessary. For one-page clearing, the two natural marking conventions are equivalent. If the comparator has served any request belonging to an online episode, it has also served that episode’s oldest request: it either cleared the oldest request in the same access or had already cleared it earlier. Conversely, serving the oldest request itself creates a mark. Thus the mark definition and the coupling of Lemma 8.1 apply unchanged, including at simultaneous deadlines when comparator actions are accounted for first.
Theorem 10.5 (Maximum-delay list update with deadlines and heterogeneity). Under (10.4), the earliest-deadline-or-threshold MTF algorithm with is deterministic and strictly -competitive against the unrestricted clairvoyant comparator, including the cost of completing every finite input. Its competitive ratio is independent of the number of pages and requests. In particular, for one fixed superadditive penalty function per page (), arbitrary per-request hard deadlines can be added without worsening the strict factor five.
Proof. During an online episode the oldest arrival remains unchanged. The functions defining are continuous between arrivals; at an arrival a new request contributes , hence does not jump up. An access of another page via MTF can only increase or preserve the rank of a still-pending page. Thus the current penalty never exceeds before its service. In particular,
All requests are completed: by (10.4), an episode’s oldest request eventually reaches penalty at least , which is unbounded, whereas its threshold is at most . Deadlines can only trigger earlier accesses. Since each access clears at least one request, only finitely many accesses occur on finite inputs, including at tied timestamps.
Use the marks in Lemma 8.1. If accesses page because a deadline is reached, the comparator must already have served request ; order comparator actions before online actions at the same timestamp for bookkeeping. Thus is marked. Consequently, every unmarked online access was caused by exact threshold hitting and incurs penalty .
Fix an unmarked online episode of page , of length . None of its requests was served by the comparator before its end, so its oldest request remains pending in the comparator throughout . The interval therefore lies within one comparator episode of page . The penalty at this online service is at most : every request it serves arrived at or after , has age at most , and obeys (10.4). Hence for every unmarked service.
Now fix a comparator episode of page having length . The unmarked online episodes contained in are pairwise disjoint. Therefore , and superadditivity and monotonicity give
At the comparator access ending , its oldest request has age ; therefore the comparator’s maximum penalty for this episode is at least by (10.4). Summing across comparator episodes and pages yields
Equations (10.5) and (10.6) verify the assumptions of Proposition 4.1. Its choice proves the strict factor . ∎
Corollary 10.6 (Hard deadlines without waiting penalties). In the same single-page-access list-update model, assume every request has a finite hard deadline, and there is no waiting penalty before the deadline. Access a page at the earliest pending deadline for that page, clear all its requests, and move it to the front. This algorithm is strictly 3-competitive against an unrestricted feasible offline schedule.
Proof. Use the marks in Lemma 8.1. Every online access is triggered by some request’s hard deadline. The comparator must have served that request no later than the same timestamp, so every online access is marked. Therefore and .
Relation to the request-specific counterexample. Proposition 11.5 allows the ratio of request-specific weights on one page to grow without bound. The theorem above instead quantifies what is retained when such heterogeneity is uniformly bounded: if and , take the baseline to be . The algorithm needs a known bound and the currently accrued request penalties; no future arrivals are required. As with the previous arbitrary-function guarantees, no generic polynomial bit-time claim is made for evaluating arbitrary penalty functions.
One-sided arrival-order domination without a common baseline
The bounded-envelope theorem assumes a common superadditive function for a page. There is a different structural condition that needs no common baseline and tolerates arbitrarily large decreases in request severity over time. It only limits how much a later request can exceed an earlier one.
Theorem 10.7 (One-sided arrival-order domination). For each request let be continuous, nondecreasing, unbounded, superadditive, and satisfy . Fix a known and suppose that, for every two requests to the same page with ,
(The condition applies in both directions at equal timestamps.) Each request may also have an arbitrary hard deadline in . Accessing a page costs its rank plus the maximum of the pending requests’ current penalties. Access a page at the first of a hard-deadline expiration or a hit of the threshold by its maximum pending penalty, where , and move that page to the front. This deterministic rule is strictly -competitive against the unrestricted clairvoyant comparator on every finite input. In particular, if later requests never have larger penalty functions than earlier requests (), the factor is 5, with no bound on the ratio of their magnitudes.
Proof. For a pending page , the maximum of its requests’ accrued penalties is continuous between arrivals; newly arriving requests have zero penalty, so it cannot jump up at an arrival. An MTF access of another page cannot lower ’s rank. Thus an access never pays more than in waiting penalty, and every access not forced by a deadline hits the threshold exactly. Every finite input is completed: the penalty of any unserved request eventually exceeds .
Mark an online page episode at the first comparator access serving any request in the episode, as in Lemma 8.1. Deadline-forced online accesses are marked because the comparator must meet the same deadlines; consequently, every unmarked online access occurs at exact threshold. Hence
Fix an unmarked online episode of page . Its oldest request remains pending in the comparator throughout , so lies in a single comparator episode for the same page, with and length . Let be any request arriving at the start of . For every request cleared by the online access ending we have . Thus the one-sided comparison (30), followed by monotonicity, gives
Since ends unmarked, it is a threshold access, so .
For all unmarked online episodes lying in , their interiors are disjoint and . The same comparator request and its superadditive function can be used for every one of them. Therefore
Here the last inequality follows because is present at the comparator access ending , with age ; its individual penalty is no more than the maximum penalty charged by that access. Summing over pages and comparator episodes yields . Together with (31), this verifies both conditions of Proposition 4.1; choosing gives the strict factor .
Corollary 10.8 (Nonincreasing request weights). Fix, for each page , a continuous, nondecreasing, unbounded, superadditive function with . Let each request for page have penalty with , where the weights are nonincreasing in arrival order and are equal among simultaneous requests of the same page. No bound on the ratio of weights is needed. The deadline-or-threshold MTF algorithm of Theorem 10.7 is strictly 5-competitive.
Proof. Each satisfies the theorem’s pointwise ordering and superadditivity hypotheses.
Why this does not contradict the negative example. Proposition 11.5 uses request weights that increase rapidly with each new arrival. The theorem covers the opposite direction, including arbitrarily steep decreases. It does not prove a constant competitive ratio for arbitrary request-specific maximum penalties.
Lower bounds and limits of the threshold analysis
The statements in this section distinguish three different conclusions: a lower bound for all deterministic algorithms, a lower bound for the particular scaled threshold rule, and failures of that rule outside its proved delay-function assumptions. They are not interchangeable.
A deterministic problem lower bound
Theorem 11.1 (One-page deterministic lower bound). No deterministic completing algorithm has competitive ratio strictly below two, even for one page with unit access cost and linear episode delay. The statement remains true when a fixed additive constant is allowed.
Proof. Fix and any finite additive constant . Choose such that . We construct requests one at a time. The first request arrives at . Given the current finite prefix, consider the algorithm’s continuation if no further request arrives. Completion requires it to access the pending page at a finite time . Choose the next arrival strictly after and at most . The next arrival can be chosen rational. Determinism ensures that the algorithm actually behaves as simulated through . After requests, stop the construction and let the algorithm complete the last request normally. There is no end-of-input notification.
Let . Each request is alone in its algorithm episode, so the algorithm pays at least . Extra accesses, if any, only increase its cost. The one-page optimum formula in Proposition 9.4 gives
For every ,
The last inequality follows separately on and . Consequently
Taking sufficiently large makes this exceed . Although the construction is adaptive, for a fixed deterministic algorithm it specifies a finite input sequence, as required for a deterministic lower bound.
Theorem 11.2 (Tight deterministic guarantee for one page). For one page of unit access cost and linear per-episode maximum delay, the algorithm that serves a pending episode exactly one time unit after its first arrival is strictly 2-competitive against the unrestricted clairvoyant optimum. Together with Theorem 11.1, the optimal deterministic competitive factor for this single-page problem is exactly 2.
Proof. For each request at time , draw the interval and let be their union. Consider any offline batch served at time , whose earliest request arrived at . All the intervals of requests in the batch are contained in . The latter interval has length , exactly the offline batch’s access-plus-maximum-delay cost. Taking the union across all batches and using subadditivity of length gives .
Let be the first arrival times of the online algorithm’s successive episodes. Each episode is cleared at . The next episode begins only after that clearing, so the intervals have disjoint interiors and are all contained in . Therefore . Each online episode costs one access plus one unit of delay, and hence . This applies to every finite input and has no additive term. The deadline-free policy needs no signal that the input has ended.
A lower bound for the scaled rank threshold
Proposition 11.3 (Reverse blocks). For every fixed and every , the scaled rank-threshold algorithm has input sequences on which its cost divided by is at least
*The construction can be repeated arbitrarily many times. Thus the rule’s competitive ratio uniform in is at least , including when an instance-independent additive constant for each fixed is allowed. In particular, the lower bound approaches at and four at .
Proof. Start from and repeatedly request the block . Separate consecutive arrivals by a fixed . Each request is served before the next arrival. At every access, its page is last in the algorithm’s list, so its rank is , its wait is , and its cost is . Each block restores the initial permutation and costs .
Keeping the initial list fixed and serving every request immediately is a feasible offline schedule of cost per block. Dividing the algorithm’s cost by this feasible upper bound on OPT gives the displayed ratio. For any smaller proposed factor at a fixed , repeating blocks makes the resulting excess cost arbitrarily large, absorbing a fixed additive constant. Finally let grow. This is a lower bound for the specified threshold algorithm, not for all algorithms.
Why the nonlinear hypotheses matter
Proposition 11.4 (Concave powers). Let , where . For every fixed , the rule that serves when its page’s episode penalty reaches times the current rank has unbounded competitive ratio, already on one page.
Proof. Put and release requests at . The rule serves every request separately at age , before the following arrival. Its total cost is . A feasible offline schedule serves all requests together at the final arrival, for cost
The ratio of these two costs grows as , and the ratio to OPT is at least as large. The excess over any proposed constant multiple of the displayed comparison cost also diverges, so an additive constant does not repair the guarantee. This disproves the fixed-scale rule, not the existence of other algorithms for concave delay.
Proposition 11.5 (Request-dependent linear weights). Suppose requests to the same page may have different positive linear weights, and the delay charge of an access is the maximum weighted waiting time among the requests it clears. For every fixed , the rule that serves when this maximum reaches times the current rank has unbounded competitive ratio, even on one page.
Proof. For , let request arrive at
Assuming earlier requests have been cleared, its weighted age reaches at
whenever a following request exists. Inductively, every request is served alone and the algorithm pays . Offline can instead serve the entire input at time one. Every weighted age then equals , so this schedule costs only . The ratio is unbounded as grows. Each instance is finite; the argument does not require an infinite input accumulating at time one. There is no conflict with a guarantee for a single fixed linear weight per page.
A limitation of averaging the global scale
Proposition 11.6 (The existing coefficient certificate). Choose a positive random scale independently of the input and run the fixed-scale rule with . Averaging the deterministic inequalities
cannot certify a uniform competitive factor strictly below five. This is only a limitation of these inequalities, not a randomized lower bound.
Proof. When the two moments are finite, the averaged spatial and delay coefficients are and . Both would have to be strictly below five for this bound to certify a factor below five for arbitrary nonnegative , . That would require
contradicting by Cauchy–Schwarz. If either moment is infinite, the corresponding averaged coefficient gives no finite improvement. The deterministic choice attains coefficient five. A sharper analysis of randomized scales, or an algorithm that resamples scales during its execution, is not ruled out by this argument.
Disclosure of AI-Assisted Research and Writing
OpenAI language-model systems, including Codex, were used extensively in developing this draft. Their contributions included proof exploration, counterexample search, implementation and independent checking of small instances, adversarial review of proofs, literature verification, and LaTeX drafting and revision. The mathematical arguments are given in full; computational checks are supplementary. Responsibility for the manuscript’s claims, citations, and final presentation remains with its authors.
References
- [1]Susanne Albers, Bernhard von Stengel, and Ralph Werchner. A combined BIT and TIMES-TAMP algorithm for the list update problem. Information Processing Letters, 56(3):135–139, 1995.
- [2]Christoph Ambühl. Offline list update is NP-hard. In Proc. ESA, pages 42–51, 2000.DOI
- [3]Yossi Azar, Shahar Lewkowicz, and Varun Suriyanarayana. List update with prediction. Proc. AAAI, 39(15):15436–15444, 2025.
- [4]Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List update with delays or time windows. In Proc. ICALP, pages 15:1–15:20, 2024.arxiv.org/abs/2304.06565
- [5]Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, and Agnieszka Tatarczuk. A 3.3904-competitive online algorithm for list update with uniform costs. In Proc. ESA, pages 76:1–76:15, 2025.arxiv.org/abs/2503.17264
- [6]Mateusz Basiak, Marcin Bienkowski, and Agnieszka Tatarczuk. An improved deterministic algorithm for the online min-sum set cover problem. In Proc. WAOA, pages 45–58, 2023.arxiv.org/abs/2306.17755
- [7]Marcin Bienkowski and Marcin Mucha. An improved algorithm for online min-sum set cover. Proc. AAAI, 37(6):6815–6822, 2023.arxiv.org/abs/2209.04870
- [8]Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas. The online min-sum set cover problem. In Proc. ICALP, pages 51:1–51:16, 2020.arxiv.org/abs/2003.02161
- [9]Tianhang Lu, Runtian Ren, and Shengcai Liu. Online covering with maximum delay under subadditive service costs. arXiv preprint arXiv:2609.32675, 2026.arxiv.org/abs/2609.32675
- [10]Tianhang Lu, Runtian Ren, Shengcai Liu, and Ke Tang. Online multi-level aggregation with maximum delay. arXiv preprint arXiv:2608.06796, 2026.arxiv.org/abs/2608.06796
- [11]Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202–208, 1985.
