Online Algorithms

Rent the GPU or buy it

A lab needs a GPU node for a project whose length nobody knows. Renting costs 40 a day; buying costs 400 once, and then the node is free for as long as it is needed. Each morning the lab learns only that the project is still running, and decides: rent one more day, or buy.

Measure money in rental-days, so renting costs 1 a day and buying costs $B=10$. If the need lasts $d$ whole days, someone who knew $d$ in advance would pay

$$\mathrm{O}\mathrm{P}\mathrm{T}(d)=min(d,B):$$

rent throughout if $d<10$, buy on day 1 otherwise. The lab does not know $d$. This module is about decisions of that kind, made before the next piece of the future is revealed and never taken back: what a good rule even means, and how to prove that one rule is the best possible.

Two obvious rules, and where each wastes

Always rent. If the project runs 40 days, the lab pays 40 against the 10 of buying on day 1, four times too much, and the factor grows with $d$ without limit.

Buy at once. If the project stops after one day, the lab pays 10 against 1.

Each rule is perfect on one side of the unknown and badly wrong on the other. We want a rule whose waste is bounded on every possible future. The deterministic rules are easy to list: "rent until day $t-1$, buy on day $t$", for some $t=1,2,\dots$, or never buy. That list is complete: for any deterministic rule, let $t$ be the first day on which it buys; no decision follows the purchase, so the rule behaves exactly like "buy on day $t$". So the whole question is which $t$ to pick.

The model: competitive ratio against an adversary

An online algorithm receives a request sequence $\sigma ={\sigma }_1{\sigma }_2\dots {\sigma }_m$ one request at a time. It must act on ${\sigma }_j$ before it sees ${\sigma }_{j+1}$, and its actions are irrevocable. $\mathrm{O}\mathrm{P}\mathrm{T}(\sigma )$ is the cost of the best offline solution, which sees all of $\sigma$ in advance.

A deterministic online algorithm ALG is $c$-competitive if there is a constant $a$ with

$$\mathrm{A}\mathrm{L}\mathrm{G}(\sigma )\le c·\mathrm{O}\mathrm{P}\mathrm{T}(\sigma )+a$$

for every sequence $\sigma$; it is strictly $c$-competitive when this holds with $a=0$. The competitive ratio is a worst case over sequences, and it is natural to picture an adversary who knows the algorithm and writes the sequence. For a deterministic algorithm the adversary can simulate every decision in advance, so it does not matter whether it writes the whole sequence first or adapts as it goes. For a randomized algorithm it does: an oblivious adversary knows the algorithm but not its coin flips and must fix $\sigma$ beforehand, while an adaptive adversary sees each decision before choosing the next request. Randomized bounds below are all against an oblivious adversary.

The additive constant matters. In a single rent-or-buy season a rule that buys on day $t$ never pays more than $t-1+B$, so a large enough $a$ would make any such rule 1-competitive. (Always renting is the exception: its cost grows with the length of the season.) For rent or buy we state strict ratios. The paging and list results below hold with $a=0$ as well, and the paging lower bound survives any constant $a$, because the adversary can make the sequence as long as it likes.

Rent or buy, solved

from fractions import Fraction

def rent_or_buy(t, d, B):
    """Paid by the rule 'buy on day t' (t=None: never) if the need lasts d days."""
    return d if t is None or d < t else (t - 1) + B

def worst_ratio(t, B, horizon):
    return max(Fraction(rent_or_buy(t, d, B), min(d, B)) for d in range(1, horizon + 1))

assert rent_or_buy(10, 10, 10) == 19 and worst_ratio(10, 10, 100) == Fraction(19, 10)
assert worst_ratio(5, 10, 100) == Fraction(14, 5)
assert worst_ratio(None, 10, 40) == 4 and worst_ratio(None, 10, 400) == 40
for B in (2, 5, 10, 50):
    ratios = {t: worst_ratio(t, B, 4 * B) for t in range(1, 3 * B + 1)}
    best = min(ratios.values())
    assert best == 2 - Fraction(1, B) and [t for t in ratios if ratios[t] == best] == [B]

Theorem. Buying on day $B$ is strictly $(2-1/B)$-competitive, and no deterministic rule has a smaller strict ratio.

Upper bound. If $d<B$, the rule has only rented and pays $d=\mathrm{O}\mathrm{P}\mathrm{T}$. If $d\ge B$, it paid $B-1$ days of rent and then $B$, a total of $2B-1$, against $\mathrm{O}\mathrm{P}\mathrm{T}=B$. The ratio is at most $(2B-1)/B=2-1/B$.

Lower bound. Take any rule "buy on day $t$". The adversary ends the need on day $t$, the evening after the purchase. The rule paid $t-1+B$ and the optimum $min(t,B)$. For $t\le B$ the ratio is $(t-1+B)/t=1+(B-1)/t$, which is at least $1+(B-1)/B=2-1/B$. For $t>B$ it is $(t-1+B)/B\ge 2$. A rule that never buys pays $d$ against $B$ and loses by any factor we like. $◻$

The best rule rents until the rent already paid is about to reach the purchase price, then buys. The asserts above check the theorem by brute force for $B=2,5,10,50$: over all buy days up to $3B$ and needs up to $4B$ days, the smallest worst ratio is $2-1/B$, reached only at $t=B$.

Randomness helps. A rule that picks its buy day at random, from a distribution the adversary knows but whose outcome it cannot see, can do better in expectation. Against an oblivious adversary, the best expected ratio a randomized rule can guarantee tends to $e/(e-1)\approx 1.58$ as $B$ grows (Karlin, Manasse, McGeoch and Owicki, 1994). This is stated here, not proved.

List update: move-to-front

Items $a,b,c,d,e$ sit in a linked list, and a request for the item at position $i$ (counting from 1) costs $i$. After an access, the requested item may be moved closer to the front for free; any other swap of two adjacent items costs 1 (a paid exchange). This is the cost model of Sleator and Tarjan.

Move-to-front (MTF) moves every requested item to the front. On the requests a d e e c e d e:

import itertools, math

def mtf_total(items, requests):
    L, total = list(items), 0
    for x in requests:
        i = L.index(x)
        total += i + 1
        L.insert(0, L.pop(i))
    return total

def kendall(a, b):
    """Adjacent swaps needed to turn order a into order b (pairs in opposite order)."""
    pos = {x: i for i, x in enumerate(b)}
    s = [pos[x] for x in a]
    return sum(s[i] > s[j] for i in range(len(s)) for j in range(i + 1, len(s)))

def list_opt(items, requests):
    """Offline optimum: paid swaps at 1 each any time, free moves forward after an access."""
    perms = list(itertools.permutations(items))
    cur = {tuple(items): 0}
    for x in requests:
        nxt = {}
        for s, c in cur.items():
            for t in perms:
                i = t.index(x)
                v = c + kendall(s, t) + i + 1
                for j in range(i + 1):                 # the free move after the access
                    u = t[:j] + (x,) + t[j:i] + t[i + 1:]
                    nxt[u] = min(nxt.get(u, math.inf), v)
        cur = nxt
    return min(cur.values())

R = "adeecede"
assert mtf_total("abcde", R) == 23
assert sum("abcde".index(x) + 1 for x in R) == 32          # the list that never moves
assert list_opt("abcde", R) == 20 and 23 <= 2 * 20 - len(R)

MTF pays 23, the list that never moves 32, and the offline optimum (brute force over all $5!=120$ orders) 20. MTF overpaid at the fifth access (c, cost 5, where the original list charges 3), but e, requested four times, stays near the front.

Why move-to-front is within a factor 2

Theorem (Sleator and Tarjan). For every request sequence of length $m$ and every algorithm $A$, online or offline, that starts from the same list and pays in the same model,

$$C_{\mathrm{M}\mathrm{T}\mathrm{F}}\le 2C_A-m,$$

where $C_A$ counts $A$'s access costs plus its paid exchanges. In particular MTF is strictly 2-competitive.

Proof, with the potential method from Amortized Analysis. Let $\Phi$ be the number of inversions between MTF's list and $A$'s list: pairs of items that the two lists hold in opposite orders. Both lists start equal, so ${\Phi }_0=0$, and $\Phi \ge 0$ always. Define MTF's amortized cost of an access as its actual cost plus the change in $\Phi$ that the access causes.

Let the requested item $x$ be at position $k$ in MTF's list and $i$ in $A$'s. Of the $k-1$ items in front of $x$ in MTF's list, say $v$ are behind $x$ in $A$'s list. The other $k-1-v$ are in front of $x$ in both lists, so there are at most $i-1$ of them:

$$k-1-v\le i-1.$$

That inequality is the step not to skip: it is the only place where MTF's cost gets tied to $A$'s. Moving $x$ to the front removes the $v$ inversions it had with those items and creates exactly $k-1-v$ new ones, with the items that are in front of $x$ in $A$'s list. So

$$k+\Delta \Phi =k+(k-1-v)-v$$

$$=2(k-v)-1\le 2i-1.$$

$A$'s own moves are charged to $A$. A free move brings $x$ forward, past items that MTF now holds behind $x$, so it only removes inversions. A paid exchange changes $\Phi$ by at most 1 and costs $A$ exactly 1. Summing over the sequence, the actual total is the amortized total minus ${\Phi }_{\text{end}}-{\Phi }_0\ge 0$, so

$$C_{\mathrm{M}\mathrm{T}\mathrm{F}}\le \sum _j(2i_j-1)+P_A\le 2C_A-m,$$

with $i_j$ the positions $A$ paid and $P_A$ its paid exchanges. $◻$

On the trace above, against the list that never moves, the amortized costs are checked below access by access.

def amortized_against(A, items, requests):
    """(MTF cost, A's position, amortized cost) per access, A a list that never moves."""
    L, rows = list(items), []
    for x in requests:
        k, i = L.index(x) + 1, A.index(x) + 1
        before = kendall(L, A)
        L.insert(0, L.pop(k - 1))
        rows.append((k, i, k + kendall(L, A) - before))
    return rows

rows = amortized_against("abcde", "abcde", R)
assert [r[2] for r in rows] == [1, 7, 9, 1, 5, 3, 3, 3]
assert all(am <= 2 * i - 1 for k, i, am in rows)

The factor 2 is nearly the truth for MTF. The adversary asks, every time, for the item at the back of MTF's list. MTF pays $n$ per request. A list that never moves pays $1+2+\dots +n=n(n+1)/2$ for every $n$ such requests, since the adversary's requests cycle through all $n$ items; so the optimum pays at most about $(n+1)/2$ per request, and the ratio on this family tends to at least $2n/(n+1)$. On abcde, the adversary's 20 requests are edcba four times: MTF pays 100, the offline optimum 60, a ratio of $5/3=2·5/6$.

def back_of_mtf(items, m):
    L, req = list(items), []
    for _ in range(m):
        req.append(L[-1])
        L.insert(0, L.pop())
    return "".join(req)

adv = back_of_mtf("abcde", 20)
assert adv == "edcba" * 4 and mtf_total("abcde", adv) == 100 and list_opt("abcde", adv) == 60

Paging: three rules and a yardstick

A cache holds $k$ pages. A request for a page that is not in the cache is a fault, costs 1, and brings the page in; if the cache is full, some page must be evicted first. Hits cost nothing, and the cache starts empty. LRU evicts the least recently used page, FIFO the page that was brought in earliest, and farthest in future (FIF), Belady's rule, evicts the cached page whose next request is farthest away, or never comes.

FIF reads the future, so it is not an online algorithm. It is the yardstick: FIF makes the fewest faults of any schedule. Belady proposed the rule in 1966; Mattson, Gecsei, Slutz and Traiger proved it optimal in 1970. Proof sketch: take an optimal schedule that agrees with FIF on the first $j$ requests. If at request $j+1$ it evicts $q$ where FIF evicts $f$, change it to evict $f$ and keep $q$, and from then on copy the old schedule until the difference first matters. Since $q$ is requested before $f$, the change never adds a fault. The case analysis of "until the difference first matters" is skipped here.

With $k=3$ and the requests 7 5 9 5 4 5 4 7 5 2 4 7:

When 4 arrives at request 5, FIF holds 7, 5, 9 and evicts 9, which is never requested again. When 2 arrives at request 10, it holds 4, 5, 7 and evicts 5, again never requested. The difference between LRU and FIFO is request 8: FIFO evicts 5, the oldest arrival, though it was requested at request 6; LRU evicts 9. FIFO then faults on 5 at request 9.

def faults(seq, k, victim):
    """Simulate a cache; victim(cache, loaded, last_used, t) picks the page to evict."""
    cache, loaded, last_used, n = set(), {}, {}, 0
    for t, p in enumerate(seq):
        if p not in cache:
            n += 1
            if len(cache) == k:
                cache.remove(victim(cache, loaded, last_used, t))
            cache.add(p)
            loaded[p] = t
        last_used[p] = t
    return n

lru_rule = lambda cache, loaded, used, t: min(cache, key=used.get)
fifo_rule = lambda cache, loaded, used, t: min(cache, key=loaded.get)

def fif_faults(seq, k):          # the future read the slow way: scan ahead from request t
    def next_use(q, t):
        return next((j for j in range(t + 1, len(seq)) if seq[j] == q), math.inf)
    return faults(seq, k, lambda cache, loaded, used, t: max(sorted(cache), key=lambda q: next_use(q, t)))

def brute_opt(seq, k):
    """Fewest faults over every eviction choice (exhaustive, small inputs only)."""
    memo = {}
    def go(t, cache):
        if t == len(seq):
            return 0
        if (t, cache) not in memo:
            p = seq[t]
            if p in cache:
                memo[t, cache] = go(t + 1, cache)
            elif len(cache) < k:
                memo[t, cache] = 1 + go(t + 1, cache | {p})
            else:
                memo[t, cache] = 1 + min(go(t + 1, cache - {q} | {p}) for q in cache)
        return memo[t, cache]
    return go(0, frozenset())

S = [7, 5, 9, 5, 4, 5, 4, 7, 5, 2, 4, 7]
assert faults(S, 3, lru_rule) == 8 and faults(S, 3, fifo_rule) == 9
assert fif_faults(S, 3) == 5 == brute_opt(S, 3)

LRU is k-competitive

Theorem (Sleator and Tarjan). With caches of the same size $k$, both starting empty, LRU makes at most $k$ times as many faults as the optimum on every sequence: it is strictly $k$-competitive. So is FIFO.

Proof. Cut the sequence into phases, left to right: each phase is as long as possible while mentioning at most $k$ distinct pages.

LRU faults at most $k$ times per phase. Once a page $p$ has been requested in a phase, the pages used more recently than $p$ are pages of the same phase, and there are at most $k-1$ of them besides $p$. So $p$ stays among the $k$ most recently used pages, and LRU keeps it, until the phase ends. Each of the phase's at most $k$ distinct pages therefore faults at most once.

The optimum faults at least once per phase. Its first request is a fault, since the cache starts empty. For every later phase, look at the requests from the second request of the previous phase through the first request of this one. Let $p$ be the previous phase's first page. These requests mention $k$ distinct pages other than $p$: the $k-1$ others of the previous phase, plus the new page that started this phase. Right after $p$ was requested, any schedule holds $p$, so it has room for only $k-1$ of those $k$ pages and must fault in this window. The windows of different phases do not overlap, so $\mathrm{O}\mathrm{P}\mathrm{T}\ge$ the number of phases, while LRU makes at most $k$ times that many faults. $◻$

For FIFO (sketch): a page that faults twice in one phase was evicted in between, after $k$ other pages were brought in, all requested in the phase: $k+1$ distinct pages, too many.

The figure's phases check out: LRU's 8 faults fall 3, 2 and 3 into the three phases, and the optimum's 5 are at least 3.

def phase_of(seq, k):
    out, seen, ph = [], set(), 0
    for p in seq:
        if p not in seen and len(seen) == k:
            ph, seen = ph + 1, set()
        seen.add(p)
        out.append(ph)
    return out

assert phase_of(S, 3) == [0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2]
assert brute_opt(S, 3) >= 3 and faults(S, 3, lru_rule) <= 3 * 3

No deterministic pager does better

Theorem. For every deterministic online paging algorithm ALG with cache size $k$ and every $m\ge k$, there is a sequence of $m$ requests on which ALG faults $m$ times and the optimum at most $k+\lceil (m-k)/k\rceil$ times. So no deterministic pager is $c$-competitive for any $c<k$, whatever additive constant it is allowed.

Proof. Use only $k+1$ pages. Since ALG is deterministic, the adversary knows its cache at all times, and always requests the one page ALG does not hold: ALG faults every time. For the optimum, look at FIF. After the first $k$ requests, when FIF faults it evicts the page among its $k$ whose next request is farthest away. Until that page comes back, only the other $k$ pages are requested, and each of FIF's other $k-1$ pages comes before it. So FIF's next fault is at least $k$ requests later, which gives at most $\lceil (m-k)/k\rceil$ faults after the first $k$ requests. As $m$ grows, $m/(k+\lceil (m-k)/k\rceil )$ tends to $k$. $◻$

For LRU the adversary's sequence is just the $k+1$ pages in a cycle. With $k=3$ and 90 requests, LRU faults 90 times and FIF 32.

Randomness helps here too. The marking algorithm marks a page when it is requested; on a fault it evicts a uniformly random unmarked page, and when every cached page is marked it first unmarks them all. Against an oblivious adversary its expected number of faults is at most $2H_k$ times the optimum, where $H_k=1+1/2+\dots +1/k\approx \ln k$, and no randomized pager does better than $H_k$ (Fiat, Karp, Luby, McGeoch, Sleator and Young, 1991). Stated, not proved. Against an adaptive adversary, which sees each eviction before choosing the next request, randomness is worth nothing: the proof above goes through unchanged, and the ratio is back to $k$.

Measure the claim

LRU against FIF on two kinds of sequences, $m=30k$ requests each: the adversary's cycle on $k+1$ pages, and requests drawn uniformly at random from $2k$ pages (seed 451; the lesson's code computes every number). Each cell is LRU's faults / FIF's faults, and the proven bound on the ratio is $k$.

import random

def cycle(k, m):
    return [j % (k + 1) for j in range(m)]

rng = random.Random(451)
table = []
for k in (3, 8, 16):
    m = 30 * k
    a = cycle(k, m)
    u = [rng.randrange(2 * k) for _ in range(m)]
    table.append((k, faults(a, k, lru_rule), fif_faults(a, k), faults(u, k, lru_rule), fif_faults(u, k)))
    assert fif_faults(a, k) == k + math.ceil((m - k) / k)
assert table == [(3, 90, 32, 39, 30), (8, 240, 37, 125, 65), (16, 480, 45, 256, 127)]
assert [(round(b / c, 2), round(d / e, 2)) for k, b, c, d, e in table] == [(2.81, 1.3), (6.49, 1.92), (10.67, 2.02)]

On the adversary's cycle the ratio climbs toward $k$, as the theorem says it must; the gap is FIF's $k$ cold faults, and it closes as $m$ grows. On random requests the same LRU stays near 2 on these runs, far from $k$. Testing an online algorithm on random inputs measures typical behaviour on those inputs and says nothing about its competitive ratio: the worst case has to be built.

In real software

Real caches approximate LRU, because exact LRU rewrites a shared list on every hit. PostgreSQL's shared buffer manager picks a victim with a clock sweep: a hand moves around the buffers, decrementing each buffer's usage count and taking the first unpinned buffer whose count is zero (StrategyGetBuffer in src/backend/storage/buffer/freelist.c). Redis's LRU eviction policies sample a few keys (maxmemory-samples, default 5) and evict the least recently used among a small pool of candidates; its source calls this an approximation of LRU (src/evict.c).

A problem that looks different

A film restorer's bench has room for four reels. The director calls for reels one at a time, in an order nobody writes down in advance, and fetching a reel from the vault takes an hour, after which some reel on the bench has to go back. Which one should go, and against what could anyone judge the restorer's choices? (Not solved here; the lab's last problem is a different one.)

Practise

In the lab you draw move-to-front with its inversion potential and check the invariant in every frame, trace LRU's cache and phases on a new sequence, write farthest-in-future so that it reads the future only once, play the adversary against paging rules you have never seen, and finish with a problem that doesn't say what it is.

Recap

• You can now: define a competitive ratio, with its adversary and its additive constant; prove that buying on day $B$ is strictly $(2-1/B)$-competitive and that no deterministic rule does better; prove $C_{\mathrm{M}\mathrm{T}\mathrm{F}}\le 2C_A-m$ with the inversion potential; prove LRU $k$-competitive by phases; and build the sequence that forces every deterministic pager to $k$.
• Invariant: online cost is charged to the optimum on every sequence: per season (rent or buy), per access through the inversion potential (move-to-front, amortized cost at most $2i-1$), and per phase (LRU: at most $k$ faults, the optimum at least 1).
• Complexity achieved: strict ratios $2-1/B$, 2 and $k$ in the worst case over all request sequences; $2-1/B$ and $k$ are optimal among deterministic algorithms. Never buying has no bounded ratio at all, and a list that never moves is only $n$-competitive.
• Failure mode: judging an online algorithm on random sequences, or against a fixed rival instead of the offline optimum. The adversary's sequence has to be built.
• In real software: PostgreSQL's clock-sweep buffer replacement and Redis's sampled LRU eviction both approximate LRU.
• Retrieval: the potential method from Amortized Analysis: why may the MTF proof add up amortized costs $2i-1$ and conclude a bound on the actual cost?

Check yourself

1. In the move-to-front proof, which inequality ties MTF's cost to $A$'s position, and why is it true?
2. Let the adversary see a randomized pager's coin flips before choosing each request. What happens to the marking algorithm's $2H_k$, and why?
3. For a cache of 3 pages, compare LRU, FIFO and FIF on 7 5 9 5 4 5 4 7 5 2 4 7. Where does FIFO lose its extra fault, and how do all three compare with the bound $k·\mathrm{O}\mathrm{P}\mathrm{T}$?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.