betaFeedback

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 55-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 55 for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor 33. Two structural conditions on request-specific penalties give factor 3+2κ3+2κ. In particular, nonincreasing request severity retains factor 55 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 Ω(m)Ω(m) gap between the best static order and dynamic reordering, and prove that the optimal deterministic factor for one page is exactly 22. 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 3+2κ3 + 2\kappa: a bounded superadditive page baseline, or pointwise domination of later requests by κ\kappa 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 Ω(m)\Omega(m) 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 10/310/3, 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 AA and OO, use

Φ=I(A,O)+2∑p markedro(p).(1)\Phi= I(A,O) + 2 \sum_{p\ \mathrm{marked}} ro(p). \tag*{(1)}

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

CA≤3CO+2BA,(2)C_A \le3C_O + 2B_A, \tag*{(2)}

where BAB_A 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 DA≤βCAD_A \le\beta C_A and βBA≤κDO\beta B_A \le\kappa D_O whenever the delay model supports this interval charge. The temporal transfer principle (Proposition 4.1) combines these conditions with (2), yielding a strict factor 3+2κ3 + 2\kappa at β=2κ/3\beta= 2\kappa/3. Ordinary linear delay has κ=1\kappa= 1, 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 mm be the number of pages and NN 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 S=m!2mS = m!2^m, so its dependence on input length is polynomial but its dependence on mm is not. Table 1 separates these guarantees from bounds on a particular online rule.

SettingResult
Linear waiting, onlineDeterministic strict factor 5; the chosen threshold rule has a lower bound approaching 10/3.
Page-wise superadditive penaltiesStrict factor 5; includes convex waiting and common exogenous calendar rates.
Hybrid with deadlinesStrict factor 5 for common page penalties; strict factor 3+2κ3 + 2\kappa for request-specific penalties within a known factor κ\kappa of a superadditive page baseline.
Arrival-ordered penaltiesStrict factor 3+2κ3 + 2\kappa under one-sided function domination; factor 5 when request severity is nonincreasing, even without bounded weight ratios.
Hard deadlines onlyStrict factor 3 with one access per pending page.
Linear waiting, offlineNP-complete decision problem; exact O(NSmlog⁡S)O(NSm\log S) arithmetic-operation algorithm, S=m!2mS = m!2^m; polynomial-time 5-approximation.
One page, linear waitingOptimal deterministic factor exactly 2; the lower bound applies even allowing an additive constant.
Fixed listExplicit optimal batching in linear time after requests are grouped by page.
Best free static orderPolynomial-time assignment formulation, but Ω(m)\Omega(m) 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 RR of acceptable items, and its access cost is the rank of the earliest item of RR 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 rr, Bienkowski and Mucha obtained a randomized O(r2)O(r^2)-competitive algorithm against the dynamic optimum, as well as an existential deterministic O(r4)O(r^4) guarantee [7]. Basiak, Bienkowski, and Tatarczuk subsequently gave a constructive deterministic O(r2)O(r^2)-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 kk into 1+⋯+k1+\cdots+k, 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 (pi,ai)(p_i,a_i), where pip_i is one of mm pages and ai≥0a_i \ge0 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 rr, the access costs rr 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 α\alpha for this first arrival. Further requests to the page join the episode without changing α\alpha. If the next access occurs at tt, the episode contributes delay t−αt-\alpha. Thus a schedule has total cost

C+D=∑accessesrank⁡(p)+#{paid exchanges}+∑episodes [α,t](t−α).(3)C + D = \sum_{\text{accesses}} \operatorname{rank}(p) + \#\{\text{paid exchanges}\} + \sum_{\text{episodes }[\alpha,t]} (t-\alpha). \tag*{(3)}

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 P(t)P(t) is the set of pending pages in a schedule, then

D=∫0∞∣P(t)∣ dt.(4)D = \int_{0}^{\infty} \lvert P(t)\rvert\,\mathrm{d}t. \tag*{(4)}

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 RR means ALG⁡(I)≤ROPT⁡(I)\operatorname{ALG}(I) \le R\operatorname{OPT}(I) for every finite timed input II. 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 β>0\beta> 0. The scaled rank-threshold rule accesses a pending page pp as soon as

t−αp≥βrA(p),(5)t-\alpha_p \ge\beta r_A(p), \tag*{(5)}

then moves pp 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

  1. Maintain the list and the oldest arrival αp\alpha_p of each pending page.

  2. When a request arrives at a nonpending page pp, set αp\alpha_p to its arrival time.

  3. Reveal all arrivals at the current time before taking an action.

  4. while some pending page satisfies t−αp≥βrA(p)t-\alpha_p \ge\beta r_A(p) do

  5. Choose one such page pp, access it, and clear its pending requests.

  6. Move pp to the front and remove its episode clock.

  7. Wait for an arrival or the next equality in (5), whichever occurs first.

Why every service hits its threshold exactly. While pp is pending, another page’s move-to-front can only preserve or increase pp’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 CAC_A for the sum of access ranks, we obtain

DA=βCA,ALG⁡=(1+β)CA.(6)D_A=\beta C_A,\qquad\operatorname{ALG}=(1+\beta)C_A. \tag*{(6)}

Since ranks never exceed mm, each episode completes within βm\beta m 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 β>0\beta> 0 and every feasible comparison schedule with access and paid-exchange cost COC_O and delay DOD_O.

ALG⁡β≤3(1+β)CO+2(1+β)βDO.(7)\operatorname{ALG}_{\beta} \le3(1+\beta)C_O+\frac{2(1+\beta)}{\beta}D_O. \tag*{(7)}

In particular, β=2/3\beta=2/3 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 β=2/3\beta=2/3. 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 [A,B,C][A, B, C] and β=2/3\beta= 2/3. Requests for BB and CC arrive at time zero. Another request for BB arrives at time 1/31/3, and a request for AA arrives at time one. The second BB request joins the existing episode; it does not restart its clock or add a second waiting charge.

At time 4/34/3, page BB has age 4/34/3 and rank two, so it is accessed and moved to the front. The list becomes [B,A,C][B, A, C]. Page AA had been due at 1+2/3=5/31 + 2/3 = 5/3, but its rank is now two and its threshold moves to 7/37/3. At time two, CC reaches its rank-three threshold. Moving it forward changes the list to [C,B,A][C, B, A] and raises AA’s rank again. Page AA 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 BB arrivals share one episode.

Access timePageRankEpisode ageList after access
4/3BB24/3[B,A,C][B, A, C]
2CC32[C,B,A][C, B, A]
3AA32[A,C,B][A, C, B]

Table 1 (PDF p. 7).

The access total is eight, and delay is 16/316/3, exactly two thirds of that total. A comparator could keep the original list, access BB at 1/31/3, CC at zero, and AA at one, paying 6+1/36 + 1/3 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 AA’s original rank would serve it at 5/35/3 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 pp, mark that page when the comparison schedule first serves the episode’s oldest request. The mark remains until the online algorithm accesses pp. Later arrivals to pp 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 BAB_A is the sum of access ranks over these unmarked services, threshold equality gives

βBA≤DO.(8)\beta B_A \le D_O. \tag*{(8)}

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.

Offline and online episodes for a fixed page

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 I(A,O)I(A,O) count unordered page pairs whose relative order differs in the two lists. If G\mathcal{G} is the set of marked pages, define

Φ=I(A,O)+2∑p∈GrO(p).(9)\Phi= I(A,O) + 2\sum_{p\in\mathcal{G}} r_O(p). \tag*{(9)}

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 pp at rank kk, while its offline rank is ℓ\ell. Let aa be the number of pages preceding pp in both lists. Moving pp to the front changes the inversion count by

ΔI=2a−(k−1).\Delta I = 2a - (k - 1).

For a marked page, clearing its episode also removes 2ℓ2\ell from the potential. Since a≤ℓ−1a \le\ell- 1, this decrease pays for the access: k+ΔΦ≤−1k + \Delta\Phi\le-1. For an unmarked page, no credit is removed, but ΔI≤k−1\Delta I \le k - 1 gives k+ΔΦ≤2kk + \Delta\Phi\le2k. These are exactly the services already covered by (8).

Offline changes pay for the credit they create. An offline access at rank ℓ\ell may create a mark of value 2ℓ2\ell. 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 ℓ−1\ell- 1 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.

EventBound used in the sum
Online access, marked page, rank kkk+ΔΦ≤0k + \Delta\Phi\le0
Online access, unmarked page, rank kkk+ΔΦ≤2kk + \Delta\Phi\le2k
Offline access and free forward move, rank ℓ\ellΔΦ≤3ℓ\Delta\Phi\le3\ell
Offline paid adjacent exchangeΔΦ≤3\Delta\Phi\le3

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

CA≤3CO+2BA.(10)C_A \le3C_O + 2B_A. \tag*{(10)}

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 AA be a feasible, completing MTF algorithm that makes no paid exchanges and clears every pending request at its accessed page. Fix a feasible comparator OO with the same initial list, and let BAB_A be the sum of ranks of AA’s accesses unmarked relative to OO. Suppose that for some β>0\beta> 0 and κ>0\kappa> 0,

DA≤βCA,βBA≤κDO.(11)D_A \le\beta C_A,\qquad\beta B_A \le\kappa D_O. \tag*{(11)}

Then

ALG≤3(1+β)CO+2κ(1+β)βDO.(12)\mathrm{ALG} \le3(1+\beta)C_O + \frac{2\kappa(1+\beta)}{\beta}D_O. \tag*{(12)}

If these conditions hold on every finite input against every feasible comparator for a fixed κ>0\kappa> 0 and β=2κ/3\beta= 2\kappa/3, then AA is strictly (3+2κ)(3 + 2\kappa)-competitive. For the fixed comparator OO, DA=BA=0D_A = B_A = 0 instead gives CA≤3COC_A \le3C_O. If there are no waiting penalties and every access is marked on every finite input against every feasible comparator, then AA is strictly 3-competitive.

The proof in § 8 combines the coupling with (4.4). For linear waiting, both conditions hold with κ=1\kappa= 1 and threshold equality gives DA=βCAD_A = \beta C_A. With deadlines, an early deadline-driven access is already marked, so equality for all online services is replaced by DA≤βCAD_A \le\beta C_A; 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 (π,P)(\pi, P): the current permutation and the pending-page set. Across a gap Δ\Delta, add Δ∣P∣\Delta|P|. 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 PP. Within the layer, paid exchanges change π\pi, while an access pays its rank, removes one page from PP, 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 S=m!2mS = m!2^m, the offline optimum can be computed in O(NSmlog⁡S)O(NSm \log S) arithmetic operations and O(Sm)O(Sm) 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 mm, rather than an exponent of mm 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 [A,B][A, B], let BB be requested at zero and AA at time ten. Accessing BB immediately and leaving it in place, then accessing AA, 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 cc and distinct arrivals t1<⋯<tqt_1 < \cdots< t_q, its optimal cost is

c+∑i=1q−1min⁡{ti+1−ti,c}.(13)c + \sum_{i=1}^{q-1} \min\{t_{i+1} - t_i, c\}. \tag*{(13)}

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 Ω(m)\Omega(m) 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 pp, fix a function fp:[0,∞)→[0,∞)f_p : [0,\infty) \to[0,\infty) that is continuous, nondecreasing, unbounded, and zero at zero. All requests of that page use the same function. An episode of duration xx pays fp(x)f_p(x), equivalently the maximum of the individual fpf_p-penalties of its requests. Assume further that

fp(x+y)≥fp(x)+fp(y)(x,y≥0).(14)f_p(x+y) \ge f_p(x)+f_p(y) \qquad(x,y \ge0). \tag*{(14)}

This includes positive page-specific linear weights and nondecreasing unbounded convex functions vanishing at zero. Different pages may use different functions, such as fp(t)=wptqpf_p(t)=w_p t^{q_p} with qp≥1q_p \ge1.

Theorem 6.1 (Page-specific waiting penalties). Access page pp when fp(t−αp)f_p(t-\alpha_p) reaches 23rA(p)\frac{2}{3}r_A(p), 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 DA=23CAD_A=\frac{2}{3}C_A. For the offline charge, consider unmarked online intervals of lengths x1,…,xsx_1,\ldots,x_s inside one offline episode of page pp, of length LL. They are disjoint, so ∑ixi≤L\sum_i x_i \le L. Hence

∑ifp(xi)≤fp(∑ixi)≤fp(L).\sum_i f_p(x_i) \le f_p\left(\sum_i x_i\right) \le f_p(L).

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 pp have an exogenous nonnegative rate wp(t)w_p(t), and charge an episode [a,b][a,b] the amount ∫abwp(t) dt\int_a^b w_p(t)\,\mathrm{d}t. 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 κ\kappa times that baseline, the combined algorithm is strictly (3+2κ)(3+2\kappa)-competitive for known κ\kappa. 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 κ\kappa 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 κ\kappa. The same argument now gives a strict 3+2κ3 + 2\kappa factor. In particular, for κ=1\kappa= 1 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 (1,…,m)(1,\ldots,m) and repeatedly request m,m−1,…,1m,m-1,\ldots,1, separating consecutive requests by H>βmH > \beta m. Every online episode finishes before the next arrival. Each requested page is at rank mm, waits βm\beta m, and costs (1+β)m(1+\beta)m. After one block the list returns to its initial order. In comparison, keeping the initial list fixed and serving immediately costs m(m+1)/2m(m+1)/2 per block. Therefore

ALGβOPT≥2(1+β)mm+1.(15)\frac{\mathrm{ALG}_{\beta}}{\mathrm{OPT}} \ge\frac{2(1+\beta)m}{m+1}. \tag*{(15)}

Repeating blocks absorbs any fixed additive constant. This family approaches 10/310/3 for our choice β=2/3\beta= 2/3. It approaches four for β=1\beta= 1, 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 f(t)=tγf(t) = t^\gamma, 0<γ<10 < \gamma< 1, a fixed threshold f(age)=βf(\text{age}) = \beta serves after time τ=β1/γ\tau= \beta^{1/\gamma}. Release NN requests at intervals 2τ2\tau. The algorithm serves them separately and pays (1+β)N(1+\beta)N. Offline may batch all of them at the last arrival for

1+[2τ(N−1)]γ.1 + [2\tau(N-1)]^\gamma.

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 β>0\beta> 0, take one page and requests i=0,…,N−1i = 0,\ldots,N-1 with

ai=1−4−i,wi=2β4i,a_i = 1 - 4^{-i}, \qquad w_i = 2\beta4^i,

and charge each batch the maximum of wi(t−ai)w_i(t-a_i) over its requests. A rule that serves when this maximum reaches β\beta clears request ii before the next one arrives, paying (1+β)N(1+\beta)N in total. At time one, however, every weighted age is exactly 2β2\beta, so a single offline batch costs 1+2β1 + 2\beta. 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 BB independently of the input and run the corresponding deterministic threshold. Averaging Theorem 3.1 gives

E[ALGB]≤3(1+E[B])CO+2(1+E[B−1])DO.(16)\mathbb{E}[\mathrm{ALG}_{B}] \le3(1+\mathbb{E}[B])C_O + 2(1+\mathbb{E}[B^{-1}])D_O. \tag*{(16)}

Both coefficients could be below five only if E[B]<2/3\mathbb{E}[B] < 2/3 and E[B−1]<3/2\mathbb{E}[B^{-1}] < 3/2, contradicting E[B]E[B−1]≥1\mathbb{E}[B]\mathbb{E}[B^{-1}] \ge1. The best uniform factor furnished by this inequality is therefore five, attained by the deterministic scale 2/32/3. 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, AA denotes the algorithm’s list and OO the comparison list. Their initial permutations are identical. We write rA(p)r_A(p) and rO(p)r_O(p) for the current ranks of page pp, and let COC_O include both accesses and paid adjacent exchanges.

A coupling for delayed move-to-front schedules

An episode of AA starts when a request arrives to a page with no pending requests and ends when AA 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 OO serves that oldest request. Retain the mark until AA ends the episode. In particular, later arrivals to a marked page do not remove its mark, even if they become pending in OO.

For the analysis, reveal all arrivals at a timestamp first, then process the actions of OO, and finally those of AA. 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 AA unmarked if its page is unmarked immediately before that access. Let BAB_A 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 AA 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 OO with the same initial list,

CA≤3CO+2BA.C_A \le3C_O + 2B_A.

The comparator may perform proactive paid adjacent exchanges and choose any permitted free forward move after each access.

Proof. Let I(A,O)I(A,O) count unordered pairs of pages whose relative orders differ between the lists. Use the potential

Φ=I(A,O)+2∑p markedrO(p).(17)\Phi= I(A,O) + 2 \sum_{p\ \mathrm{marked}} r_O(p). \tag*{(17)}

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 AA to a page pp of rank kk, and write ℓ=rO(p)\ell= r_O(p). Let aa be the number of pages preceding pp in both lists. Among the k−1k-1 pages crossed by the move to front, exactly aa create an inversion and the other k−1−ak-1-a remove one. Thus

ΔI=2a−(k−1),a≤ℓ−1.(18)\Delta I = 2a - (k - 1), \qquad a \le\ell- 1. \tag*{(18)}

If pp is marked, ending its episode removes the term 2ℓ2\ell from the potential. The ranks and marks of other pages in OO do not change, so

k+ΔΦ=k+2a−(k−1)−2ℓ≤−1≤0.k + \Delta\Phi= k + 2a - (k - 1) - 2\ell\le-1 \le0.

If pp is unmarked, the marked-rank term is unchanged and ΔI≤k−1\Delta I \le k - 1, giving

k+ΔΦ≤2k−1≤2k.k + \Delta\Phi\le2k - 1 \le2k.

Consequently all accesses of AA satisfy

CA+∑actions of AΔΦ≤2BA.(19)C_A + \sum_{\text{actions of } A} \Delta\Phi\le2B_A. \tag*{(19)}

Next consider an access by OO to a page pp of rank ℓ\ell, including its chosen free forward move. If this access first serves the oldest request of AA's current episode for pp, mark pp before accounting for its free move. This increases the second term of (17) by 2ℓ2\ell. A forward move through h≤ℓ−1h \le\ell- 1 positions increases the inversion count by at most hh. When pp is marked, its rank decreases by hh, whereas at most hh 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 2ℓ+h≤3ℓ2\ell+ h \le3\ell.

If pp was already marked, the same argument applies without the new-mark cost. If pp remains unmarked, its forward move increases the marked-rank term by at most 2h2h and the inversion count by at most hh. Its total increase is again at most 3ℓ3\ell. This case also covers comparison accesses that serve no request from a current episode of AA.

Finally, a paid adjacent exchange by OO 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 Φ\Phi by at most three. Summing comparison actions gives

∑actions of OΔΦ≤3CO.(20)\sum_{\text{actions of } O} \Delta\Phi\le3C_O. \tag*{(20)}

Combining (19) and (20), and using the zero initial potential, we obtain

CA+Φfinal≤3CO+2BA.C_A + \Phi_{\mathrm{final}} \le3C_O + 2B_A.

Dropping the nonnegative final potential proves the claim. No condition on the final permutations is needed. □\square

Proof of Proposition 4.1. By Lemma 8.1 and the two temporal bounds,

ALG=CA+DA≤(1+β)CA≤3(1+β)CO+2(1+β)BA≤3(1+β)CO+2κ(1+β)βDO.\mathrm{ALG} = C_A + D_A \le(1+\beta)C_A \le3(1+\beta)C_O + 2(1+\beta)B_A \le3(1+\beta)C_O + \frac{2\kappa(1+\beta)}{\beta}D_O.

For β=2κ/3\beta= 2\kappa/3, both coefficients equal 3+2κ3 + 2\kappa. If DA=BA=0D_A = B_A = 0, Lemma 8.1 instead gives ALG=CA≤3CO\mathrm{ALG} = C_A \le3C_O for the fixed comparator. Applying the respective bound on every finite input against every feasible comparator proves the competitive guarantees, since AA is feasible and completing. The initial potential is zero and the final potential nonnegative, so no additive term is needed. □\square

Threshold equality and delay charging

Fix β>0\beta> 0. The scaled rank-threshold algorithm accesses a pending page pp when its oldest pending age reaches βrA(p)\beta r_A(p) 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 βrA(p)\beta r_A(p). Every episode beginning at 00 ends by α+βm\alpha+ \beta m, where mm is the number of pages. In particular,

DA=βCA,ALG=(1+β)CA.D_A = \beta C_A,\qquad\mathrm{ALG} = (1+\beta)C_A.

Proof. A new episode starts at age zero and has a positive threshold. Moving any other page to the front leaves pp’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 mm, so an episode cannot persist beyond age βm\beta m. 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,

βBA≤DO.\beta B_A \le D_O.

Proof. Consider an unmarked algorithm episode for page pp, beginning at α\alpha and ending at tt. Its oldest request has not been served by OO before the algorithm’s access. Thus pp is pending in OO throughout [α,t)[\alpha,t). The interval’s length is exactly β\beta 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 OO. 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 β>0\beta> 0, every finite input, and every feasible comparison schedule OO,

ALG⁡β≤3(1+β)CO+2(1+β)βDO.(21)\operatorname{ALG}_{\beta} \le3(1+\beta)C_O + \frac{2(1+\beta)}{\beta}D_O. \tag*{(21)}

Thus its strict competitive factor is at most (1+β)max⁡{3,2/β}(1+\beta)\max\{3,2/\beta\}. Taking β=2/3\beta= 2/3 gives factor five; taking β=1\beta= 1 gives factor six.

Proof. Lemmas 8.2 and 8.3 verify the temporal assumptions of Proposition 4.1 with κ=1\kappa= 1. 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 αp+βrA(p)\alpha_p + \beta r_A(p) over pending pages, unless an arrival occurs earlier. A scan of the list updates ranks and finds this minimum in O(m)O(m) arithmetic operations per event. There are NN request arrivals and at most NN accesses, so chronologically presented input can be processed in O(Nm)O(Nm) arithmetic operations and O(m)O(m) working memory. For β=2/3\beta= 2/3 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 NN or the last arrival time.

Offline computation and complexity

This section concerns the linear-delay model. Let NN be the number of requests and let m≥1m \ge1 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 mm 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 rr and its subsequent free move advances it by hh positions, replace the access and free move by hh paid adjacent exchanges. This produces the same permutation and pending set and costs h≤r−1<rh \le r-1 < r. 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 tj<tj+1t_j < t_{j+1}. Move all operations in the open interval (tj,tj+1)(t_j,t_{j+1}) to immediately after the operations originally performed at tjt_j, 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 P(t)P(t) be its pending-page set. Its linear waiting cost is

D=∫∣P(t)∣ dt.(22)D = \int|P(t)|\,\mathrm{d}t. \tag*{(22)}

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 S=m!2mS = m!2^m. The offline optimum can be computed in O(NSmlog⁡S)O(NSm\log S) arithmetic operations, using O(Sm)O(Sm) 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 mm, 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 rr followed by a free forward move of hh positions can instead be implemented by hh paid forward exchanges before the access and then an access at rank r−hr-h. The total cost is still rr, 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 (π,P)(\pi,P) for each permutation π\pi of the mm pages and each subset PP of pages. Its arcs encode instantaneous actions:

  • An adjacent exchange in π\pi has cost one and leaves PP unchanged.

  • Accessing p∈Pp \in P has cost rank⁡π(p)\operatorname{rank}_{\pi}(p), removes pp from PP, and leaves the permutation unchanged.

Every vertex has O(m)O(m) 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 t1<⋯<tKt_1 < \cdots< t_K be the distinct arrival epochs, with K≤NK \le N, and let RjR_j be the set of pages requested at tjt_j. Let Fj(π,P)F_j(\pi, P) be the minimum cost just after the actions at tjt_j, with waiting already charged through tjt_j. To pass from epoch j−1j-1 to epoch jj, each state (π,P)(\pi, P) first pays (tj−tj−1)∣P∣(t_j-t_{j-1})|P| and then activates the new requests. Thus its cost is a candidate seed for state (π,P∪Rj)(\pi, P \cup R_j). Take the minimum when several predecessor states give the same seed. Apply multi-source Dijkstra to these seeds to obtain FjF_j 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

min⁡πFK(π,∅).\min_{\pi} F_K(\pi,\varnothing).

In particular, all requests are completed; no constraint is imposed on the terminal list. Empty input has value zero.

The graph has SS vertices and O(Sm)O(Sm) arcs. Multi-source Dijkstra with a binary heap costs O(Smlog⁡S)O(Sm \log S) per epoch, and two cost vectors suffice between epochs. The graph and the two vectors use O(Sm)O(Sm) 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 mm.

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 BB, deciding whether there is a complete schedule of cost at most BB is NP-complete.

Proof. For membership in NP, use the arrival-layer normal form. There are at most mm 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 m(m−1)/2m(m-1)/2. The same replacement applies before the first and after the last access at the epoch. The resulting certificate has O(Nm3)O(Nm^3) 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 mm pages and its request sequence have length NN. Put request ii at time iHiH, where H=Nm+1H = Nm + 1. Serving every request immediately without changing the list is feasible and costs at most NmNm. If a request were still pending at the next arrival, its page episode would eventually pay waiting cost at least H>NmH > Nm. 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 rr followed by a free forward move of hh positions can be replaced by hh paid swaps before the access, followed by an access at rank r−hr-h, 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 r−1r-1 to rr adds exactly NN 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 cc with distinct arrival times t1<⋯<tqt_1 < \cdots< t_q, its optimum cost is zero if q=0q=0 and otherwise equals

Gp(c)=c+∑i=1q−1min⁡{ti+1−ti,c}.(23)G_p(c) = c + \sum_{i=1}^{q-1} \min\{t_{i+1}-t_i,c\}. \tag*{(23)}

Summing these quantities over pages gives the fixed-list optimum, which can be computed in O(N+m)O(N+m) 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 cc plus the sum of the gaps internal to that batch. Starting with one access cost cc, 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 cc. 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 Gp(r)G_p(r) from (23) for each page pp and each possible rank r∈{1,…,m}r \in\{1,\ldots,m\}. Assigning pages to distinct ranks is a minimum-cost perfect matching in the bipartite graph of pages and ranks, where edge (p,r)(p,r) has cost Gp(r)G_p(r). 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 (m+1)/2(m+1)/2 more expensive than the unrestricted offline optimum.

Proof. Start the unrestricted schedule in order (p1,…,pm)(p_1,\ldots,p_m). For an integer K≥1K \ge1, give KK consecutive requests to p1p_1, then KK to p2p_2, and so on through pmp_m. Space all arrivals by H>mH > m, so every consecutive gap of a given page exceeds every possible rank. Each page has KK requests, and Proposition 9.4 gives cost KrKr if it is assigned rank rr. Thus every freely chosen static permutation costs Km(m+1)/2Km(m+1)/2.

A feasible dynamic schedule serves every request immediately and moves the accessed page to the front. The first access in phase jj has rank jj; the other K−1K-1 accesses of that phase have rank one. Its total cost is mK+m(m−1)/2mK+m(m-1)/2. Hence the static optimum divided by unrestricted OPT is at least

Km(m+1)/2mK+m(m−1)/2=K(m+1)2K+m−1.\frac{Km(m+1)/2}{mK+m(m-1)/2}=\frac{K(m+1)}{2K+m-1}.

Letting KK 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 DA≤βCAD_A \le\beta C_A and βBA≤κDO\beta B_A \le\kappa D_O, 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 pp, fix a function fp:[0,∞)→[0,∞)f_p : [0,\infty) \to[0,\infty) which is continuous, nondecreasing, and unbounded, with fp(0)=0f_p(0)=0. Assume also that

fp(x+y)≥fp(x)+fp(y)for all x,y≥0.(24)f_p(x+y) \ge f_p(x)+f_p(y) \quad\text{for all } x,y \ge0. \tag*{(24)}

An episode beginning at α\alpha and served at tt incurs penalty fp(t−α)f_p(t-\alpha). Since the function is nondecreasing and is common to all requests on page pp, this is the maximum of the requests’ individual penalties in that episode. Functions may differ between pages. The algorithm triggers when fp(t−αp)f_p(t-\alpha_p) first reaches βrA(p)\beta r_A(p).

Lemma 10.1 (Superadditive interval charge). Under these assumptions, every algorithm access occurs with penalty βrA(p)\beta r_A(p), every finite input is completed, and

βBA≤DO.\beta B_A \le D_O.

Here DOD_O 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 fpf_p has flat portions. Since fpf_p is unbounded, an episode ends no later than the first age at which fpf_p reaches βm\beta m. 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 x1,…,xsx_1,\ldots,x_s and that comparison episode has length LL, the intervals are disjoint and ∑i=1sxi≤L\sum_{i=1}^{s} x_i \le L. Superadditivity and monotonicity imply

∑i=1sfp(xi)≤fp(∑i=1sxi)≤fp(L).\sum_{i=1}^{s} f_p(x_i) \le f_p\left(\sum_{i=1}^{s} x_i\right) \le f_p(L).

Each term on the left is β\beta times its algorithm access rank. Summing these inequalities over comparison episodes proves βBA≤DO\beta B_A \le D_O.

Theorem 10.2 (Superadditive episode penalties). For the functions above, scaled rank-threshold MTF satisfies

ALG⁡β≤3(1+β)CO+2(1+β)βDO\operatorname{ALG}_{\beta} \le3(1+\beta)C_O+\frac{2(1+\beta)}{\beta}D_O

against every feasible comparator. In particular, β=2/3\beta=2/3 gives a strict competitive factor of five.

Proof. The marked-rank coupling gives CA≤3CO+2BAC_A \le3C_O+2B_A. By Lemma 10.1, BA≤DO/βB_A \le D_O/\beta, and exact threshold equality gives DA=βCAD_A=\beta C_A. Combining these facts proves the result.

Continuous nondecreasing unbounded convex functions with value zero at zero satisfy (24). Indeed, for x+y>0x+y>0, convexity gives fp(x)≤xfp(x+y)/(x+y)f_p(x)\le xf_p(x+y)/(x+y) and the corresponding inequality for yy; 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 pp, let wp:[0,∞)→[0,∞)w_p:[0,\infty)\to[0,\infty) be an exogenous locally integrable rate, shared by the two schedules. An episode [α,t][\alpha,t] has penalty

Fp(α,t)=∫αtwp(s) ds.(25)F_p(\alpha,t)=\int_{\alpha}^{t}w_p(s)\,\mathrm{d}s. \tag*{(25)}

Nonnegativity makes this the maximum of the integrals from the individual request arrival times to tt, 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 βrA(p)\beta r_A(p). To ensure completion of every finite input, assume

∫u∞wp(s) ds=∞for every page p and every finite u≥0.(26)\int_u^\infty w_p(s)\,\mathrm{d}s=\infty\quad\text{for every page }p\text{ and every finite }u\ge0. \tag*{(26)}

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 DA=βCAD_A=\beta C_A and βBA≤DO\beta B_A\le D_O.

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 α\alpha reaches penalty βm\beta m in finite time, so it must be served by then. Summing equality at service gives DA=βCAD_A=\beta C_A.

As before, each unmarked algorithm episode occupies an interval during which the same page is pending in OO. 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 OO. Equivalently,

βBA=∑p∫s in an unmarkedalgorithm episode of pwp(s) ds≤∑p∫0∞wp(s) 1{p is pending in O at s} ds=DO.\beta B_A = \sum_p \int_{\substack{s\ \text{in an unmarked}\\\text{algorithm episode of }p}} w_p(s)\,\mathrm{d}s \le\sum_p \int_0^\infty w_p(s)\,1\{p\text{ is pending in }O\text{ at }s\}\,\mathrm{d}s = D_O.

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

ALGβ≤3(1+β)CO+2(1+β)βDO.\mathrm{ALG}_{\beta} \le3(1+\beta)C_O+\frac{2(1+\beta)}{\beta}D_O.

In particular, β=2/3\beta=2/3 gives a strict factor of five without knowledge of future rates.

Proof. Apply Lemma 8.1 and Lemma 10.3, then use ALGβ=(1+β)CA\mathrm{ALG}_{\beta}=(1+\beta)C_A.

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 NN. 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 vv, let p(v)p(v) be its page, ava_v its arrival, dv∈[av,∞]d_v\in[a_v,\infty] its deadline, and fv:[0,∞)→[0,∞)f_v:[0,\infty)\to[0,\infty) its waiting penalty. A page access at time tt clears all requests then pending at that page and incurs the penalty max⁡vfv(t−av)\max_v f_v(t-a_v) 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 dvd_v and fvf_v when request vv arrives.

Fix a known κ≥1\kappa\ge1. For each page pp, assume there is a continuous, nondecreasing, unbounded, superadditive function FpF_p, with Fp(0)=0F_p(0)=0, such that every request vv for pp satisfies

Fp(x)≤fv(x)≤κFp(x)(x≥0).(27)F_p(x)\le f_v(x)\le\kappa F_p(x)\qquad(x\ge0). \tag*{(27)}

All fvf_v are assumed continuous, nondecreasing, and zero at zero. The functions fvf_v need not be identical within a page.

For a pending page pp write Hp(t)=max⁡v∈PA(p,t)fv(t−av)H_p(t)=\max_{v\in P_A(p,t)}f_v(t-a_v) and let δp(t)\delta_p(t) be the earliest deadline among its pending requests. Fix β>0\beta>0. Serve pp at the first time that either Hp(t)=βrA(p)H_p(t)=\beta r_A(p) or t=δp(t)t=\delta_p(t), then move pp 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 β=2κ/3\beta= 2\kappa/3 is deterministic and strictly (3+2κ)(3 + 2\kappa)-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 (κ=1\kappa= 1), 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 HpH_p are continuous between arrivals; at an arrival a new request contributes fv(0)=0f_v(0) = 0, hence HpH_p 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 βrA(p)\beta r_A(p) before its service. In particular,

DA≤βCA.(28)D_A \le\beta C_A. \tag*{(28)}

All requests are completed: by (10.4), an episode’s oldest request eventually reaches penalty at least Fp(t−a)F_p(t-a), which is unbounded, whereas its threshold is at most βm\beta m. 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 AA accesses page pp because a deadline dvd_v is reached, the comparator must already have served request vv; order comparator actions before online actions at the same timestamp for bookkeeping. Thus pp is marked. Consequently, every unmarked online access was caused by exact threshold hitting and incurs penalty βrA(p)\beta r_A(p).

Fix an unmarked online episode I=[a,t]I=[a,t] of page pp, of length xx. None of its requests was served by the comparator before its end, so its oldest request remains pending in the comparator throughout II. The interval II therefore lies within one comparator episode JJ of page pp. The penalty at this online service is at most κFp(x)\kappa F_p(x): every request it serves arrived at or after aa, has age at most xx, and obeys (10.4). Hence βrA(p)≤κFp(x)\beta r_A(p) \le\kappa F_p(x) for every unmarked service.

Now fix a comparator episode JJ of page pp having length LL. The unmarked online episodes I1,…,IsI_1,\ldots,I_s contained in JJ are pairwise disjoint. Therefore ∑j=1s∣Ij∣≤L\sum_{j=1}^{s}|I_j| \le L, and superadditivity and monotonicity give

β∑j=1srA(p;Ij)≤κ∑j=1sFp(∣Ij∣)≤κFp(∑j=1s∣Ij∣)≤κFp(L).\beta\sum_{j=1}^{s} r_A(p;I_j) \le\kappa\sum_{j=1}^{s} F_p(|I_j|) \le\kappa F_p\left(\sum_{j=1}^{s}|I_j|\right) \le\kappa F_p(L).

At the comparator access ending JJ, its oldest request has age LL; therefore the comparator’s maximum penalty for this episode is at least Fp(L)F_p(L) by (10.4). Summing across comparator episodes and pages yields

βBA≤κDO.(29)\beta B_A \le\kappa D_O. \tag*{(29)}

Equations (10.5) and (10.6) verify the assumptions of Proposition 4.1. Its choice β=2κ/3\beta= 2\kappa/3 proves the strict factor 3+2κ3+2\kappa. ∎

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 BA=0B_A = 0 and ALG=CA≤3CO=3OPT\mathrm{ALG} = C_A \le3C_O = 3\mathrm{OPT}.

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 fv(x)=wvFp(x)f_v(x) = w_vF_p(x) and wv∈[wp,κwp]w_v \in[w_p,\kappa w_p], take the baseline to be wpFpw_pF_p. The algorithm needs a known bound κ\kappa 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 vv let fv:[0,∞)→[0,∞)f_v : [0,\infty) \to[0,\infty) be continuous, nondecreasing, unbounded, superadditive, and satisfy fv(0)=0f_v(0) = 0. Fix a known κ≥1\kappa\ge1 and suppose that, for every two requests u,vu,v to the same page with au≤ava_u \le a_v,

fv(x)≤κfu(x)for every x≥0.(30)f_v(x) \le\kappa f_u(x) \qquad\text{for every } x \ge0. \tag*{(30)}

(The condition applies in both directions at equal timestamps.) Each request may also have an arbitrary hard deadline in [av,∞][a_v,\infty]. 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 βrA(p)\beta r_A(p) by its maximum pending penalty, where β=2κ/3\beta= 2\kappa/3, and move that page to the front. This deterministic rule is strictly (3+2κ)(3 + 2\kappa)-competitive against the unrestricted clairvoyant comparator on every finite input. In particular, if later requests never have larger penalty functions than earlier requests (κ=1\kappa= 1), the factor is 5, with no bound on the ratio of their magnitudes.

Proof. For a pending page pp, 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 pp’s rank. Thus an access never pays more than βrA(p)\beta r_A(p) 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 βm\beta m.

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

CA≤3CO+2BA,DA≤βCA.(31)C_A \le3C_O + 2B_A,\qquad D_A \le\beta C_A. \tag*{(31)}

Fix an unmarked online episode I=[a,t]I = [a,t] of page pp. Its oldest request remains pending in the comparator throughout II, so II lies in a single comparator episode J=[b,s]J = [b,s] for the same page, with b≤ab \le a and length L=s−bL = s - b. Let uu be any request arriving at the start bb of JJ. For every request vv cleared by the online access ending II we have av≥a≥ba_v \ge a \ge b. Thus the one-sided comparison (30), followed by monotonicity, gives

fv(t−av)≤κfu(t−av)≤κfu(t−a)=κfu(∣I∣).f_v(t-a_v) \le\kappa f_u(t-a_v) \le\kappa f_u(t-a) = \kappa f_u(|I|).

Since II ends unmarked, it is a threshold access, so βrA(p;I)≤κfu(∣I∣)\beta r_A(p;I) \le\kappa f_u(|I|).

For all unmarked online episodes I1,…,IhI_1,\ldots,I_h lying in JJ, their interiors are disjoint and ∑j=1h∣Ij∣≤L\sum_{j=1}^{h}|I_j| \le L. The same comparator request uu and its superadditive function fuf_u can be used for every one of them. Therefore

β∑j=1hrA(p;Ij)≤κ∑j=1hfu(∣Ij∣)≤κfu(∑j=1h∣Ij∣)≤κfu(L)≤κDO(J).\beta\sum_{j=1}^{h} r_A(p;I_j) \le\kappa\sum_{j=1}^{h} f_u(|I_j|) \le\kappa f_u\left(\sum_{j=1}^{h}|I_j|\right) \le\kappa f_u(L) \le\kappa D_O(J).

Here the last inequality follows because uu is present at the comparator access ending JJ, with age LL; its individual penalty is no more than the maximum penalty charged by that access. Summing over pages and comparator episodes yields βBA≤κDO\beta B_A \le\kappa D_O. Together with (31), this verifies both conditions of Proposition 4.1; choosing β=2κ/3\beta= 2\kappa/3 gives the strict factor 3+2κ3+2\kappa.

Corollary 10.8 (Nonincreasing request weights). Fix, for each page pp, a continuous, nondecreasing, unbounded, superadditive function FpF_p with Fp(0)=0F_p(0)=0. Let each request vv for page pp have penalty wvFp(x)w_vF_p(x) with wv>0w_v>0, 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 fv=wvFpf_v = w_vF_p 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 1≤c<21 \le c < 2 and any finite additive constant bb. Choose ε>0\varepsilon> 0 such that δ=2−c−cε>0\delta= 2-c-c\varepsilon> 0. We construct requests one at a time. The first request arrives at a1=0a_1=0. 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 si≥ais_i \ge a_i. Choose the next arrival ai+1a_{i+1} strictly after sis_i and at most si+εs_i+\varepsilon. The next arrival can be chosen rational. Determinism ensures that the algorithm actually behaves as simulated through sis_i. After NN requests, stop the construction and let the algorithm complete the last request normally. There is no end-of-input notification.

Let τi=si−ai\tau_i=s_i-a_i. Each request is alone in its algorithm episode, so the algorithm pays at least ∑i=1N(1+τi)\sum_{i=1}^{N}(1+\tau_i). Extra accesses, if any, only increase its cost. The one-page optimum formula in Proposition 9.4 gives

OPT=1+∑i=1N−1min⁡{ai+1−ai,1}≤1+∑i=1N−1min⁡{τi+ε,1}.\mathrm{OPT}=1+\sum_{i=1}^{N-1}\min\{a_{i+1}-a_i,1\}\leq1+\sum_{i=1}^{N-1}\min\{\tau_i+\varepsilon,1\}.

For every x≥0x\geq0,

1+x−cmin⁡{x+ε,1}≥1+x−cmin⁡{x,1}−cε≥2−c−cε=δ.1+x-c\min\{x+\varepsilon,1\}\geq1+x-c\min\{x,1\}-c\varepsilon\geq2-c-c\varepsilon=\delta.

The last inequality follows separately on x≤1x\leq1 and x≥1x\geq1. Consequently

ALG−c OPT≥(N−1)δ+1−c.\mathrm{ALG}-c\,\mathrm{OPT}\geq(N-1)\delta+1-c.

Taking NN sufficiently large makes this exceed bb. 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 aa, draw the interval [a,a+1][a,a+1] and let UU be their union. Consider any offline batch served at time tt, whose earliest request arrived at amin⁡a_{\min}. All the intervals of requests in the batch are contained in [amin⁡,t+1][a_{\min},t+1]. The latter interval has length 1+t−amin⁡1+t-a_{\min}, exactly the offline batch’s access-plus-maximum-delay cost. Taking the union across all batches and using subadditivity of length gives ∣U∣≤OPT|U|\leq\mathrm{OPT}.

Let a1,…,aKa_1,\ldots,a_K be the first arrival times of the online algorithm’s successive episodes. Each episode is cleared at aj+1a_j+1. The next episode begins only after that clearing, so the intervals [aj,aj+1][a_j,a_j+1] have disjoint interiors and are all contained in UU. Therefore ∣U∣≥K|U|\geq K. Each online episode costs one access plus one unit of delay, and hence ALG=2K≤2∣U∣≤2OPT\mathrm{ALG}=2K\leq2|U|\leq2\mathrm{OPT}. 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 β>0\beta>0 and every m≥1m\geq1, the scaled rank-threshold algorithm has input sequences on which its cost divided by OPT\mathrm{OPT} is at least

2(1+β)mm+1.\frac{2(1+\beta)m}{m+1}.

*The construction can be repeated arbitrarily many times. Thus the rule’s competitive ratio uniform in mm is at least 2(1+β)2(1+\beta), including when an instance-independent additive constant for each fixed mm is allowed. In particular, the lower bound approaches 10/310/3 at β=2/3\beta=2/3 and four at β=1\beta=1.

Proof. Start from (1,…,m)(1,\ldots,m) and repeatedly request the block m,m−1,…,1m,m-1,\ldots,1. Separate consecutive arrivals by a fixed H>βmH>\beta m. Each request is served before the next arrival. At every access, its page is last in the algorithm’s list, so its rank is mm, its wait is βm\beta m, and its cost is (1+β)m(1+\beta)m. Each block restores the initial permutation and costs (1+β)m2(1+\beta)m^2.

Keeping the initial list fixed and serving every request immediately is a feasible offline schedule of cost m(m+1)/2m(m+1)/2 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 mm, repeating blocks makes the resulting excess cost arbitrarily large, absorbing a fixed additive constant. Finally let mm 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 f(t)=tγf(t)=t^\gamma, where 0<γ<10<\gamma<1. For every fixed β>0\beta>0, the rule that serves when its page’s episode penalty reaches β\beta times the current rank has unbounded competitive ratio, already on one page.

Proof. Put τ=β1/γ\tau=\beta^{1/\gamma} and release NN requests at 0,2τ,…,2τ(N−1)0,2\tau,\ldots,2\tau(N-1). The rule serves every request separately at age τ\tau, before the following arrival. Its total cost is N(1+β)N(1+\beta). A feasible offline schedule serves all requests together at the final arrival, for cost

1+[2τ(N−1)]γ.1+[2\tau(N-1)]^\gamma.

The ratio of these two costs grows as Ω(N1−γ)\Omega(N^{1-\gamma}), 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 β>0\beta>0, the rule that serves when this maximum reaches β\beta times the current rank has unbounded competitive ratio, even on one page.

Proof. For i=0,…,N−1i=0,\ldots,N-1, let request ii arrive at

ai=1−4−i,wi=2β4i.a_i=1-4^{-i},\qquad w_i=2\beta4^i.

Assuming earlier requests have been cleared, its weighted age reaches β\beta at

si=ai+12⋅4i<ai+34⋅4i=ai+1s_i=a_i+\frac{1}{2\cdot4^i}<a_i+\frac{3}{4\cdot4^i}=a_{i+1}

whenever a following request exists. Inductively, every request is served alone and the algorithm pays N(1+β)N(1+\beta). Offline can instead serve the entire input at time one. Every weighted age then equals wi(1−ai)=2βw_i(1-a_i)=2\beta, so this schedule costs only 1+2β1+2\beta. The ratio is unbounded as NN 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 BB independently of the input and run the fixed-scale rule with β=B\beta=B. Averaging the deterministic inequalities

ALG⁡β≤3(1+β)CO+2(1+β−1)DO\operatorname{ALG}_{\beta}\leq3(1+\beta)C_O+2(1+\beta^{-1})D_O

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 3(1+E[B])3(1 + \mathbb{E}[B]) and 2(1+E[B−1])2(1 + \mathbb{E}[B^{-1}]). Both would have to be strictly below five for this bound to certify a factor below five for arbitrary nonnegative COC_O, DOD_O. That would require

E[B]<23,E[B−1]<32,\mathbb{E}[B] < \frac{2}{3}, \qquad\mathbb{E}[B^{-1}] < \frac{3}{2},

contradicting E[B]E[B−1]≥1\mathbb{E}[B]\mathbb{E}[B^{-1}] \ge1 by Cauchy–Schwarz. If either moment is infinite, the corresponding averaged coefficient gives no finite improvement. The deterministic choice B=2/3B = 2/3 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. [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. [2]Christoph Ambühl. Offline list update is NP-hard. In Proc. ESA, pages 42–51, 2000.DOI
  3. [3]Yossi Azar, Shahar Lewkowicz, and Varun Suriyanarayana. List update with prediction. Proc. AAAI, 39(15):15436–15444, 2025.
  4. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

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

views · 12

downloads · 1

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents