Abstract
Standard worst-case analysis often yields overly pessimistic results that fail to reflect real-world algorithmic performance. This paper examines resource augmentation, a theoretical framework that compares an online algorithm to an offline optimal benchmark handicapped by fewer resources. Through case studies in paging, routing, and scheduling, we demonstrate how modest resource increases—such as doubling cache size or network capacity—can significantly improve competitive ratios, providing a more realistic theoretical foundation for system design and explaining why simple heuristics often excel in practice.
Introduction
In theoretical computer science, competitive analysis is the standard tool for evaluating online algorithms. By comparing a "protagonist" algorithm against an all-knowing "offline optimal" benchmark, researchers seek to bound worst-case performance. However, this "apples-to-apples" comparison frequently produces results that are "absurdly pessimistic." For instance, in online paging, the Least Recently Used (LRU) algorithm is theoretically $k$ times worse than optimal (where $k$ is cache size), yet it performs exceptionally well in practice.
Resource augmentation addresses this discrepancy by "handicapping" the benchmark, offering an "apples-to-slightly-smaller-apples" comparison. This approach, popularized by Tim Roughgarden, shifts the focus from absolute optimality to performance relative to a slightly less capable adversary, bridging the gap between theoretical bounds and empirical observations.
Methods and Case Studies
The paper utilizes mathematical proofs across three major domains to illustrate the power of resource augmentation:
1. Online Paging
The analysis compares LRU with a cache of size $k$ to an optimal algorithm (FIF) with a smaller cache $h < k$. The proof involves partitioning request sequences into maximal blocks containing at most $k$ distinct requests to bound the number of faults.
The competitive ratio is fundamentally tied to the number of requests that can force a fault relative to the cache capacity difference between the protagonist and the benchmark.
2. Selfish Routing
In network routing, "Price of Anarchy" analysis often predicts infinite delays when users act selfishly. Resource augmentation compares the cost of selfish equilibrium flow at a certain traffic rate $r$ to an optimal centralized flow handling slightly higher traffic $(1+\delta)r$.
3. Non-Clairvoyant Scheduling
The Shortest Elapsed Time First (SETF) algorithm, which lacks knowledge of job durations, is evaluated by granting it a faster processor than the optimal Shortest Remaining Processing Time (SRPT) algorithm.
Additionally, the paper introduces "Loosely Competitive" analysis, a statistical refinement proving that algorithms like LRU are near-optimal for the vast majority of resource configurations, rather than just a single worst-case point.
Key Results
The application of resource augmentation yields significantly tighter and more meaningful bounds:
- Paging: LRU with cache size $k$ is approximately 2-competitive against an optimal algorithm with cache size $k/2$. This is a massive improvement over the standard $k$-competitive result.
- Routing: Doubling network capacity ensures that selfish routing costs are lower than the optimal costs on the original, unaugmented network. For many common models (e.g., M/M/1 queues), this "selfish" cost is strictly better than the "optimal" cost on the original capacity.
- Scheduling: SETF with a $(1+\epsilon)$ speed boost achieves a $(1 + 1/\epsilon)$-competitive ratio against unit-speed SRPT.
- Loose Competitiveness: For any request sequence, LRU is either highly competitive or has a negligible fault rate for all but a small $\delta$ fraction of possible cache sizes.
Discussion and Conclusion
Resource augmentation provides a practical "Two-Step Recipe" for system design: first, estimate the resources an "ideal" (but impossible) algorithm requires to hit a target; second, double those resources for a simple, real-world implementation to guarantee comparable performance.
While results can be sensitive to model parameters, this framework successfully bridges the gap between pessimistic theory and observed practice. It suggests that many "bad" theoretical results in algorithmic theory are simply waiting for a resource augmentation makeover to reveal their true utility.
Summary updated