Online Algorithms and Competitive Analysis

An online problem is one in which the input arrives as a sequence of requests `σ = (r₁, r₂, …, rₙ)`, and an algorithm must produce a response to `rᵢ` before it sees `r_{i+1}, r_{i+2}, …`. This is in contrast to the offline setting, where the whole sequence `σ` is available before any decision is made. Many classical algorithmic problems (shortest path, sorting, MST) are naturally offline; online problems arise whenever decisions have real-time deadlines: cache management, job scheduling with arrivals, network routing, financial hedging, and matching markets are all online by nature. To measure quality without assuming a distribution over inputs, we compare against the best possible offline algorithm on the same sequence, denoted `OPT(σ)`. This offline optimum is a moving target: for one sequence it is the cost of one strategy, for another sequence it is the cost of a completely different strategy — it is defined instance by instance as the infimum cost achievable with full knowledge of `σ`. An online algorithm `ALG` is c-competitive (for minimization problems) if there exists a constant `a ≥ 0`, independent of `σ`, such that ``` cost_ALG(σ) ≤ c · cost_OPT(σ) + a for every input sequence σ. ``` The smallest such `c` is the competitive ratio of `ALG`. (For maximization problems the inequality flips: `cost_ALG(σ) ≥ (1/c) · cost_OPT(σ) − a`.) The additive constant `a` is a technical convenience — it allows an algorithm to be penalized on short, unlucky sequences without being disqualified by them — but for most natural problems one can prove strict competitiveness with `a = 0`. Competitive analysis is deliberately adversarial: we imagine an adversary who, knowing the algorithm's (possibly randomized) strategy in advance, constructs the worst possible sequence `σ` to maximize the ratio `cost_ALG(σ)/cost_OPT(σ)`. This is a worst-case guarantee, exactly analogous to how the approximation ratio bounds worst-case solution quality for NP-hard problems — the difference is that here the "hardness" comes from a temporally adversarial input rather than a computationally adversarial instance space. When randomization is introduced, the adversary is assumed oblivious: it fixes the entire sequence in advance, without seeing the algorithm's coin flips, and we compare the algorithm's expected cost to `OPT`. (Stronger adaptive-adversary models exist but the oblivious model is the standard baseline and is what all the ratios below use.)

Case study 1: Ski rental (the canonical warm-up)

You are about to ski for an unknown number of days. Renting skis costs `$1`/day; buying skis costs `$B` once, after which skiing is free. You must decide, each morning, whether to rent again or buy — without knowing whether this is your last ski day. This is the prototypical rent-or-buy problem, and it models any scenario with a recurring cost versus a one-time investment (buying vs. leasing hardware, caching a computation vs. recomputing it, JIT-compiling vs. interpreting a code path). The break-even algorithm: rent for the first `B − 1` days; if you are still skiing on day `B`, buy. ``` BREAK-EVEN-SKI-RENTAL(B): day ← 0 bought ← false while trip continues: day ← day + 1 if bought: ski for free today continue if day < B: rent today, pay $1 else // day == B buy skis, pay$B bought ← true ```

Claim: this algorithm is 2-competitive, and no deterministic algorithm can do better. Upper bound proof. Let `n` be the (unknown, adversarially chosen) total number of ski days.

• If `n < B`: the algorithm only ever rents, paying `n`. OPT also would have rented (buying costs `B > n`), so `OPT = n`. Ratio is exactly 1.
• If `n ≥ B`: the algorithm pays `(B − 1)` in rent plus `B` to buy, total `2B − 1`. OPT, knowing `n ≥ B` in advance, buys on day 1, paying `B`. So the ratio is

``` (2B − 1) / B = 2 − 1/B < 2. ``` In both cases `cost_ALG(σ) ≤ 2 · cost_OPT(σ)`, so the algorithm is (strictly) 2-competitive. Lower bound proof (optimality among deterministic algorithms). Any deterministic algorithm commits, in advance, to some day `k` on which it will buy if it hasn't stopped. An adversary who knows `k` simply ends the trip on day `k` — the worst possible moment. Two sub-cases:

• If the adversary stops the trip on day `k − 1` (one day before the algorithm would buy), the algorithm has paid `k − 1` in rent, while OPT (knowing the trip is `k−1` days) pays `min(k−1, B)`.
• If the adversary continues to day `k`, forcing the buy, the algorithm pays `(k − 1) + B`, while OPT pays `min(k, B)`.

Optimizing the adversary's choice of `k` against any fixed deterministic threshold shows the ratio cannot be pushed below `2 − 1/B` for any strategy — the break-even point `k = B` is exactly the threshold that balances these two failure modes, and no other threshold does better. Hence 2 is the optimal deterministic competitive ratio for ski rental (in the limit `B → ∞`, the ratio approaches exactly 2, and no deterministic algorithm beats it).

Randomization helps. If the algorithm may randomize its buying day according to a carefully chosen distribution over `{1, …, B}`, the expected competitive ratio against an oblivious adversary drops to `e/(e−1) ≈ 1.58`, strictly better than the deterministic bound of 2. This mirrors a recurring theme: randomized online algorithms can provably beat the best possible deterministic one, because the adversary must commit to a sequence before seeing the coin flips.

Case study 2: Paging / caching

A cache holds `k` pages; a sequence of page requests arrives one at a time. On a hit (requested page already in cache) there is no cost. On a miss, the algorithm must evict some page from the cache to make room, incurring one unit of cost, and cannot see future requests when deciding whom to evict. The offline optimum, Bélády's algorithm (evict the page whose next use is furthest in the future, or is never used again), is known to be optimal offline — but it requires knowledge of the future and is thus not implementable online. ``` LRU-PAGING(k): // Least-Recently-Used online algorithm cache ← empty set, |cache| ≤ k for each request p in the input sequence: if p ∈ cache: mark p as most-recently-used // hit, no cost else: if |cache| == k: evict the least-recently-used page in cache insert p into cache, mark as most-recently-used cost ← cost + 1 // miss ```

Claim: LRU (and in fact every "reasonable" deterministic algorithm) is k-competitive, and this is the best possible ratio for any deterministic online paging algorithm. Upper bound sketch (LRU is k-competitive). Partition the request sequence into maximal blocks such that each block contains exactly `k` distinct page misses under LRU (the last block may be shorter). Within any such block of `k` distinct pages, an offline algorithm with a cache of size `k` can have at most one miss on the pages that were already resident before the block began, because a block by construction touches `k` distinct new pages and the cache only holds `k` slots — forcing at least one eviction somewhere is unavoidable once `k+1` distinct pages have been seen since a slot was last free. Careful accounting (the standard potential function or phase-partition argument) shows LRU incurs at most `k` misses per block while OPT incurs at least 1, giving a ratio of `k`. Lower bound (deterministic paging cannot beat k). Fix any deterministic algorithm `ALG` with cache size `k`. An adversary who knows `ALG`'s eviction rule can always request the one page, among `k+1` candidate pages, that `ALG` currently does not have cached — forcing a miss on every single request. Meanwhile an offline algorithm, seeing the whole sequence, only needs to evict a page when a new page among the `k+1` candidates is requested for the first time in a while — and with `k+1` total pages cycling and a cache of size `k`, OPT can arrange to miss only once every `k` requests (it evicts the one candidate page not needed again soonest, à la Bélády). This forces the ratio `ALG`/`OPT` up to `k` in the worst case, matching the upper bound exactly. So k is the tight, optimal deterministic competitive ratio for paging with cache size `k` — a clean, famous result.

Randomization helps again. The randomized MARKING algorithm — mark a page on access, evict a uniformly random unmarked page on a miss, unmark everything once all pages are marked — achieves a competitive ratio of `Θ(log k)` (specifically `2 H_k − 1` where `H_k` is the `k`-th harmonic number) against an oblivious adversary, an exponential improvement over the deterministic bound of `k`. This is one of the most striking demonstrations in the whole field that hiding your randomness from the adversary is a genuinely powerful resource, not just an analytical convenience.

Time and space complexity of the algorithms themselves are usually modest — the interesting complexity in this topic is not computational cost but the information-theoretic cost of not knowing the future, quantified via the competitive ratio.

• Ski rental: `O(1)` time per day, `O(1)` space (just a counter and a boolean). The competitive-ratio analysis is `O(1)` bookkeeping — the two-case argument above.
• LRU paging: with a doubly linked list plus a hash map from page → list node, both lookup and "move to front" take `O(1)` amortized time, and the structure uses `O(k)` space for a cache of size `k`. The `k`-competitiveness proof requires only the phase-partition argument, not any extra runtime cost.
• MARKING (randomized paging): `O(1)` expected time per request with an appropriate data structure tracking marked/unmarked pages, `O(k)` space; the `Θ(log k)` ratio is a purely analytical result about expected cost, not a runtime cost.

Correctness of the competitive-ratio claims rests on two complementary arguments, and it is worth being explicit about the proof pattern, since it recurs across almost every online problem: 1. Upper bound (the algorithm is at least this good). Exhibit an explicit accounting scheme — a potential function, a charging argument, or an explicit case split — that bounds `cost_ALG(σ)` in terms of `cost_OPT(σ)` for every sequence `σ`, with no assumption on `σ`'s distribution. In ski rental this was a two-case split; in paging it was the phase/block decomposition. 2. Lower bound (no algorithm — in this model — can do better). Construct an adversary strategy that, played against an arbitrary algorithm of the given type (deterministic, or randomized against an oblivious adversary), forces the ratio up to the claimed bound. This is what proves optimality, not just correctness — it is the online-algorithms analogue of an NP-hardness reduction: it certifies that no cleverer algorithm within the model can escape the bound. Both halves are necessary: an upper bound alone only shows one algorithm is "good enough," while the matching lower bound shows the problem itself, not the particular algorithm, is inherently this hard online. When the two bounds coincide (as in ski rental's `2` and paging's `k`), the ratio is called tight, and we have fully characterized the online price of not knowing the future.

Honest tradeoffs. Competitive analysis is a worst-case framework by design — it deliberately ignores the "typical" input distribution a real system might see, which is both its strength (no assumptions needed, robust guarantees) and its weakness (an algorithm can be competitively "optimal" yet perform poorly on realistic, non-adversarial traffic; LRU with ratio `k` is far better in practice than the worst case suggests, because real access patterns exhibit locality that the adversary's construction ignores). Refinements such as access-graph models, loose competitiveness, and comparing against a restricted class of offline algorithms exist precisely to recover more realistic guarantees, at the cost of extra modeling assumptions.

Trace the ski-rental algorithm with `B = 4` (buy price $4) against three different adversarial trip lengths, and compare to the true offline optimum for each.

The worst ratio, `7/4 = 1.75`, occurs exactly at the break-even trip length `n = B = 4` and never gets worse no matter how much longer the trip runs, since both ALG's and OPT's costs saturate at `2B − 1` and `B` respectively. This matches the general bound `2 − 1/B = 2 − 1/4 = 1.75` derived above — confirming the formula on a concrete instance, not just asymptotically. Now trace LRU paging with cache size `k = 3` on the request sequence `A, B, C, A, D, A, B, C`:

LRU incurs 5 misses (steps 1,2,3,5,7) and 3 hits out of 8 requests. The offline optimum with foresight (Bélády's rule: evict the page whose next use is furthest away) can do strictly better here: at step 5, knowing that `B` is not needed again but `A` is needed at step 6, Bélády would still evict `B` (matching LRU in this case) — but on longer adversarially constructed sequences the gap between LRU and Bélády widens toward the full factor of `k`, which is exactly what the tight lower-bound construction (cycling through `k+1` pages) is designed to expose. This small trace illustrates the mechanism — eviction under uncertainty — even though it does not itself hit the full worst-case ratio, which requires a longer, carefully adversarial sequence over `k+1` pages.

Competitive analysis crystallized as a named framework in the 1980s, though its roots trace to earlier work on real-time scheduling and rent-to-buy tradeoffs.

Operating systems and hardware caches. Virtual memory page-replacement, CPU cache eviction (LRU-approximations like the clock algorithm), and CDN edge-cache policies are all direct engineering instances of the online paging problem; the k-competitiveness bound explains precisely why no deterministic eviction rule can be a silver bullet, and it motivates practical heuristics (LRU-K, ARC, CLOCK) that trade provable worst-case guarantees for better locality-aware average behavior.

Networking and routing. Online algorithms for buffer management, packet scheduling under unknown arrival patterns, and adaptive routing all use competitive-ratio analysis to bound worst-case degradation versus an omniscient offline router.

Financial and resource-allocation systems. The ski-rental tradeoff directly models cloud-instance reservation decisions (reserve vs. on-demand pricing), currency-conversion timing, and any "commit now vs. wait" decision under uncertainty; competitive analysis gives provable worst-case bounds where classical decision theory would need a (possibly unjustified) probability model.

Online matching and ad allocation. Ad-exchange platforms matching arriving queries to advertisers, and ride-sharing platforms matching arriving riders to drivers, are modeled as online bipartite matching — the Karp–Vazirani–Vazirani algorithm's `1 − 1/e` competitive ratio for randomized online matching underlies theoretical analyses of real ad-auction systems.

Algorithms with predictions. Modern research augments classical online algorithms with untrusted machine-learned forecasts (e.g., predicted future page-access patterns, predicted job sizes), asking for algorithms that are provably competitive in the worst case yet perform close to OPT when predictions are accurate — directly extending the framework developed here, and connecting online algorithms to the broader landscape of Heuristics and Local Search and modern learning-augmented systems design.

Ask the tutor: How does the randomized MARKING algorithm's Θ(log k) competitive ratio proof actually work, step by step?