Deciding without knowing the future, and measuring how much that costs against an opponent who knew it all along.
Every algorithm so far received its whole input before producing an answer. An online algorithm gets the input piece by piece and must commit to a decision on each piece before seeing the rest, with no chance to revise. Cache eviction, elevator dispatch, and ski rental are all like this. Since you cannot expect optimality, the field measures quality differently: by the competitive ratio, the worst-case ratio between what the online algorithm spends and what an omniscient offline algorithm would have spent.
| Offline | Online | |
|---|---|---|
| Input | Available in full before starting | Arrives one request at a time |
| Decisions | Made with complete knowledge | Committed irrevocably, one per request |
| Goal | The optimum | Stay within a bounded factor of the optimum |
| Measured by | Running time | Competitive ratio |
A is c-competitive if there is a constant k such that for every request sequence σ,costₐ(σ) ≤ c · costOPT(σ) + kwhere OPT is the optimal offline algorithm. The additive constant k forgives startup effects; when k = 0 the algorithm is strictly c-competitive.
The smallest interesting example, and the one that teaches the technique.
You are learning to ski. Renting costs £1 per day; buying costs £B once. Each morning you might quit for good, and you do not know when. Rent or buy?
d days pays min(d, B): rent if d < B, buy on day one otherwise.d.B - 1 days, then buy on day B. This is 2-competitive, and no deterministic algorithm does better.Why 2: if you quit before day B, you paid exactly the optimum. If you reach day B, you have paid B - 1 in rent plus B to buy, total 2B - 1, while the optimum is B. The ratio is (2B-1)/B < 2.
Why no deterministic algorithm beats 2: an adversary watches for the day you buy and ends the season immediately afterwards, making your purchase worthless. Buying earlier makes that waste relatively larger; buying later means more rent paid before it.
The chapter’s main problem. A cache holds k pages. Requests arrive one at a time. A hit is free; a miss requires fetching the page and, if the cache is full, evicting one. Minimise misses.
Chapter 15 established the offline optimum: Belady’s rule, evict the page whose next request is furthest in the future. Online, that information does not exist.
| Policy | Evicts | Competitive ratio |
|---|---|---|
| LRU (least recently used) | The page unused for longest | k |
| FIFO | The page loaded earliest | k |
| LIFO | The page loaded most recently | Not competitive at all |
| LFU (least frequently used) | The page requested fewest times | Not competitive |
| Belady (offline) | Furthest next use | 1, by definition |
k-competitive, where k is the cache size. The proof partitions the request sequence into phases, each containing requests to exactly k distinct pages. LRU incurs at most k misses in a phase; the optimal algorithm must incur at least one, because each new phase introduces a page not in the cache at the phase boundary. Ratio k.k-competitive. So LRU and FIFO are optimal among deterministic policies.The adversary argument is short and worth knowing. Restrict attention to k + 1 distinct pages, so the cache can never hold them all. The adversary simulates the algorithm and, at each step, requests the one page not currently cached. The online algorithm therefore misses on every single request.
Meanwhile the offline optimum, using Belady, misses at most once every k requests: when it evicts the page whose next use is furthest away, that page is not requested again for at least k steps. Ratio: k.
Ω(n lg n) sorting bound in Chapter 8. No amount of cleverness gets a deterministic policy below k. The only way out is to stop being deterministic.The adversary above depends on predicting exactly which page the algorithm holds. Randomize and it cannot.
MARKER is 2Hₖ-competitive, where Hₖ = 1 + 1/2 + … + 1/k ≈ ln kCache size k | Deterministic bound | Randomized bound ≈ 2 ln k |
|---|---|---|
| 10 | 10 | ~5.9 |
| 100 | 100 | ~10.4 |
| 1000 | 1000 | ~15 |
k into one that grows logarithmically. The mechanism is the same as randomized quicksort in Chapter 7: the adversary must fix the input before seeing your coin flips, so it can no longer target you specifically. The competitive ratio becomes an expected ratio, against an oblivious adversary that knows your algorithm but not its random choices.| Problem | Question | Known result |
|---|---|---|
| List update | Reorder a linked list to speed future searches | Move-to-front is 2-competitive |
| Load balancing | Assign arriving jobs to m machines | Greedy least-loaded is (2 - 1/m)-competitive |
| Bin packing | Pack arriving items into fewest bins | First-fit is 1.7-competitive |
k-server | Move k servers to serve requests in a metric space | Generalises caching; the k-server conjecture is still open |
| Secretary problem | Hire the best candidate, one irrevocable choice | Skip n/e, succeed with probability 1/e (Chapter 5) |
c-competitive means costₐ(σ) ≤ c · costOPT(σ) + k for every sequence. It is a worst-case, adversarial measure.k-competitive for a cache of size k. LFU and LIFO are not competitive at all — unaged frequency counts never decay.k. The adversary keeps requesting the one page you do not hold; the offline optimum misses only once per k requests.2Hₖ-competitive, roughly 2 ln k — logarithmic instead of linear.(2 - 1/m)-competitive; first-fit bin packing is 1.7-competitive.Chapter 28 returns to concrete computation with matrix operations: solving systems of linear equations by LU decomposition, inverting matrices, and least-squares approximation — the numerical core that Chapter 29’s linear programming and Chapter 33’s machine learning both stand on.