Online Algorithms and Competitive Analysis

Core Idea

Online algorithms must make irrevocable decisions as input arrives, without knowledge of future requests. Competitive analysis measures performance by comparing the online algorithm's cost to the optimal offline algorithm (which sees the entire input in advance). The competitive ratio is the worst-case ratio of online cost to offline optimal cost. The ski rental problem illustrates the core tension: buy skis (high upfront cost, free future use) or rent (low per-use cost, no commitment). The deterministic optimal strategy achieves competitive ratio 2; randomization improves this to e/(e-1) ≈ 1.58. For paging (cache management), LRU achieves optimal deterministic competitive ratio k (cache size), while randomized marking algorithms achieve O(log k). These results reveal a fundamental gap between deterministic and randomized online computation.

Explainer

Many real-world computational problems are inherently online: a cache manager decides which page to evict before knowing future accesses; a scheduler assigns jobs to machines as they arrive; a market maker sets prices before seeing orders. Online algorithm theory provides a framework for reasoning about irrevocable decisions under uncertainty, with competitive analysis as the primary performance measure.

The ski rental problem is the simplest interesting example. You need skis for an unknown number of days. Buying costs B; renting costs 1/day. The optimal deterministic strategy rents for B-1 days, then buys — this guarantees a competitive ratio of 2 - 1/B against any season length. The proof that no deterministic strategy does better uses an adversarial argument: whatever day t the algorithm plans to buy, the adversary ends the season on day t to maximize the ratio. Randomization helps: by buying on a randomly chosen day drawn from an appropriate distribution, the expected competitive ratio drops to e/(e-1) ≈ 1.58. This gap between 2 and 1.58 illustrates a recurring theme — randomization fundamentally helps in online settings.

The paging problem is the canonical online problem with deep results. With a cache of size k, the deterministic competitive ratio is exactly k: LRU, FIFO, and CLOCK all achieve it, and no deterministic algorithm does better. The lower bound proof constructs an adversarial sequence on k+1 pages that forces k times more faults than the offline optimal (Bélády's MIN algorithm). Randomization dramatically improves this: the randomized marking algorithm achieves competitive ratio H_k = O(log k), and this is tight against oblivious adversaries. The exponential gap (k vs log k) shows that hiding eviction decisions from the adversary is enormously valuable.

Competitive analysis has limitations. It measures worst-case performance against the omniscient offline optimum, which can be overly pessimistic — real inputs are rarely adversarial. This has motivated alternative frameworks: resource augmentation (give the online algorithm more resources than the offline optimum), smoothed competitive analysis (add random noise to adversarial inputs), and beyond-worst-case models using predictions or advice. These extensions bridge the gap between the clean theoretical framework of competitive analysis and the practical reality that online algorithms often perform much better than their competitive ratios suggest.