Cover

Harvard University · 1:24:56 · Watch on YouTube

Summary

A university lecture in two halves. The first half completes the analysis of MARK, the randomized paging algorithm of Fiat et al., proving it is 2·H_K competitive via a phase-based argument on "clean" and "stale" pages, then proving a matching-up-to-constants Ω(log K) lower bound for any paging algorithm using a uniformly random request sequence and coupon collector. A survey interlude covers what is known and still open: the H_K-optimal algorithms of McGeoch–Sleator and Achlioptas et al., an apparently open factor-2 gap under resource augmentation, and the k-server problem with its own decades-old factor-2 gap. The second half introduces the online primal-dual framework of Buchbinder and Naor — an LP/duality recap, the online constraint-arrival model with monotone variables, the approximate complementary slackness lemma, and a worked re-derivation of 2-competitive ski rental in that language.

Classification: educational video (university lecture, proof-driven).

flowchart TD
  R["Lecture 9"] --> P["Part I — Randomized paging"]
  R --> Q["Part II — Online primal-dual"]
  P --> P1["MARK algorithm<br/>phases, clean/stale"]
  P1 --> P2["Proof: 2·H_K competitive"]
  P2 --> P3["Lower bound Ω(log K)"]
  P3 --> P4["Open problems:<br/>resource augmentation, k-server"]
  Q --> Q1["LP + duality recap<br/>covering ↔ packing"]
  Q1 --> Q2["Ski rental LP<br/>+ online model"]
  Q2 --> Q3["Approximate<br/>complementary slackness"]
  Q3 --> Q4["2-competitive<br/>ski rental (α=1, β=2)"]

Topics

  1. Lecture roadmap — what the lecture promises to cover and what it actually reaches.
  2. The MARK algorithm, phases, and clean/stale pages — the algorithm, the phase decomposition, and all the notation for the proof.
  3. Proof that MARK is 2·H_K competitive — the OPT lower bound, the MARK upper bound, and where the factor of 2 is lost.
  4. Lower bound: Ω(log K) for randomized paging — random sequence over K+1 pages plus coupon collector.
  5. State of the art, open problems, and generalizations — H_K-optimal algorithms, resource augmentation, k-server, weighted paging.
  6. Linear programming and duality recap — covering/packing LPs and the dual derived as the best provable lower bound.
  7. Ski rental as an LP, and what "online" means for an LP — the primal/dual pair and the monotone constraint-arrival model.
  8. Lemma: approximate complementary slackness — the α·β guarantee that powers the framework.
  9. The primal-dual 2-competitive ski rental algorithm — the algorithm and its α = 1, β = 2 analysis.

Key takeaways

  • MARK is 2·H_K competitive, where H_K = 1 + 1/2 + … + 1/K = Θ(ln K); the bound comes from two per-phase facts — OPT pays at least max(ℓ_i − d_i, d'_i) and MARK pays at most ℓ_i · H_K in expectation (12:13, 13:00, 30:25).
  • The factor of 2 comes from a single step: replacing max(ℓ_i − d_i, d'_i) with the average of the two terms so the d terms telescope across phases (15:55, 16:32).
  • The randomness only buys you the stale requests: clean requests cost ℓ_i deterministically, while the s-th stale request misses with probability exactly c/(K − s), summing to ℓ_i·(H_K − H_{ℓ_i}) (24:59, 27:25, 29:43).
  • No paging algorithm beats Ω(log K): on a uniform random sequence over K+1 pages, any algorithm pays M/(K+1) while furthest-in-the-future OPT faults only once per Θ(K log K) requests by coupon collector — a log K gap (32:59, 36:33, 37:07).
  • MARK's factor of 2 is not necessary: McGeoch & Sleator (Algorithmica 1991) hit exactly H_K, matching the lower bound, and Achlioptas et al. (TCS 2000) gave a simpler algorithm and analysis at the same ratio (15:23, 39:14).
  • Two factor-2 gaps are flagged as open: under resource augmentation (your cache K, OPT's h) Young's 2·ln(K/(K−h+1)) still sits a factor of 2 above his own ln(K/(K−h+1)) lower bound, and for k-server the work function algorithm's 2K−1 sits a factor of 2 above the K deterministic lower bound — open for 20+ years (41:13, 41:48, 44:56).
  • The k-server randomized frontier: Bansal, Buchbinder, Mądry & Naor (2011) achieved roughly log²K · log³n · log log n, the first polylog bound, but the target is polylog(K) with no dependence on n (45:58, 46:34).
  • The dual is not an arbitrary definition — it is the LP whose optimum is the best lower bound provable by taking non-negative combinations of the primal constraints, which makes weak duality (OPT_P ≥ OPT_D) immediate (59:06, 1:00:00, 1:02:21).
  • Approximate complementary slackness converts construction into a ratio: feasible x, y satisfying the α/β near-tightness conditions imply cᵀx ≤ α·β·bᵀy ≤ α·β·OPT (1:15:32, 1:17:58).
  • Ski rental via primal-dual gives exactly 2: raising y_i until a dual constraint is tight makes both primal conditions perfectly tight (α = 1), while possibly setting both x and z_i to 1 gives β = 2 (1:23:09, 1:24:01).
  • The online LP model is what makes the framework non-trivial: rows of A arrive one at a time, must be satisfied immediately, and variables start at 0 and only increase — otherwise you could just re-solve the LP each step (1:09:12, 1:09:38).