Online Algorithms & Competitive Analysis

competitive ratio · ski rental · paging · randomization

1:00

How to measure and bound the cost of making irrevocable decisions without knowing the future, using competitive ratio, ski rental, paging/LRU, randomisation, and the secretary problem.

By the end, you can

Explain what makes an algorithm online and why OPT is an offline, not online, benchmark.
Define competitive ratio and compute it for a concrete input/output pair.
Apply the ski rental break-even rule and verify the 2-competitive bound by computing the ratio (2B−1)/B.
State why no deterministic ski rental algorithm achieves ratio below 2.
Explain the phase argument proving LRU is k-competitive for paging.
Describe the k+1-page adversary construction and use it to prove the deterministic lower bound of k for paging.
Contrast deterministic and randomised competitive ratios for both ski rental and paging, and explain why an oblivious adversary cannot defeat randomisation.
Describe the Marking algorithm and its ~2 ln k expected competitive ratio.
State the Move-To-Front competitive ratio and what cost model it uses.
Describe the 1/e observation cutoff for the secretary problem and state the resulting success probability.

Up next in Advanced Algorithms, Math & PL Theory