• Overview and Model
• Ski Rental Problem
• k-Server and Paging
• Competitive Ratios and Yao's Principle
• Exercises

• Online model: input arrives sequentially; decisions must be made irrevocably without knowledge of the future.
• Competitive ratio: worst-case over inputs of ALG/OPT for minimization (or OPT/ALG for maximization).
• Randomization: compare E[ALG] to OPT in oblivious-adversary model; use Yao's minimax principle for lower bounds.

// Deterministic 2-competitive: rent until cost equals buy, then buy.
function skiRentalDet(rentPerDay, buyCost, days) {
  let spent = 0; let own = false;
  for (let d = 1; d <= days; d++) {
    if (!own) {
      if (spent + rentPerDay < buyCost) { spent += rentPerDay; }
      else { spent += buyCost; own = true; }
    }
  }
  return spent;
}

// Randomized e/(e-1)-competitive: buy on day T ~ Geometric(p) with p=1/(e-1)
function skiRentalRand(rentPerDay, buyCost, days, rng=Math.random) {
  const p = 1/(Math.E - 1); // ~0.582
  let own = false, spent = 0;
  for (let d = 1; d <= days; d++) {
    if (!own && rng() < p) { spent += buyCost; own = true; }
    if (!own) spent += rentPerDay;
  }
  return spent;
}

• Deterministic bound: 2-competitive (optimal).
• Randomized bound: e/(e−1)-competitive against an oblivious adversary.

Paging (Caching)

Cache of size k; sequence of page requests; fault if not in cache.

// Deterministic: LRU and FIFO are k-competitive; LFU can be unbounded.
// Randomized: Marking algorithms (Randomized Marking) are O(log k)-competitive; lower bound Ω(log k).

k-Server

• On general metrics, deterministic competitive ratio ≤ 2k−1 (work function algorithm achieves this up to constants).
• On line/trees, better bounds exist; for paging metric (uniform), reduces to caching.

• Potential functions: amortize changes in state vs. OPT.
• Adversaries: oblivious vs. adaptive; competitive analysis typically uses oblivious.
• Yao's principle: lower bound for randomized algorithms via distributions and deterministic algorithms.

1. Simulate LRU, FIFO, and Randomized Marking on random request sequences; measure empirical fault ratios.
2. Implement the deterministic ski-rental strategy and compare to OPT when the number of days is known.
3. Design a potential function for LRU vs. OPT for paging and derive the k-competitive bound.