Online Algorithms
Online algorithms must make irrevocable decisions as input arrives, without knowledge of future requests; their quality is measured by competitive analysis against an optimal algorithm that sees the whole input in advance.
Definition
An online algorithm receives its input as a sequence of requests and must respond to each one immediately and irrevocably without seeing future requests; its competitive ratio is the worst-case ratio of its cost to the cost of an optimal offline algorithm that knows the entire request sequence.
Scope
This topic covers algorithms that process input sequentially and commit to decisions before later input is known, and the competitive-ratio framework used to evaluate them against an optimal offline adversary. It includes classic problems — paging and caching, list update, the ski-rental problem, the k-server problem, and online scheduling and bin packing — and the role of randomization in improving competitive ratios against weaker adversaries.
Core questions
- How are online algorithms evaluated when the future is unknown?
- What does the competitive ratio measure, and what is the offline adversary?
- How do classic problems like paging and ski rental illustrate online trade-offs?
- How can randomization improve competitiveness against an oblivious adversary?
- What lower bounds limit how competitive any online algorithm can be?
Key concepts
- online versus offline
- competitive ratio
- offline adversary
- paging and caching
- list update
- ski-rental problem
- k-server problem
- randomized competitiveness
Key theories
- Competitive analysis
- Competitive analysis judges an online algorithm by the worst-case ratio between its cost and that of an optimal offline algorithm, giving a guarantee that holds against any input sequence rather than relying on assumptions about the input.
- Randomization against oblivious adversaries
- Randomized online algorithms can achieve strictly better competitive ratios than any deterministic one against an oblivious adversary, because the adversary must fix the input without knowing the algorithm's random choices.
Clinical relevance
Online algorithms model decisions that systems make in real time without future knowledge: cache and page replacement in operating systems and CPUs, data-structure self-organization, dynamic resource allocation and load balancing, and rent-or-buy decisions in cloud computing. Competitive analysis gives worst-case guarantees for such reactive systems.
History
Competitive analysis was introduced by Sleator and Tarjan in 1985 through their study of list-update and paging rules, reframing the evaluation of online algorithms around comparison with an optimal offline solution. The framework expanded through the k-server problem and randomized online algorithms in the 1990s, surveyed in Borodin and El-Yaniv's 1998 monograph.
Key figures
- Daniel Sleator
- Robert Tarjan
- Allan Borodin
- Ran El-Yaniv
Related topics
Seminal works
- sleator1985
- borodin1998
- cormen2009
Frequently asked questions
- What is the competitive ratio?
- It is the worst-case ratio of an online algorithm's cost to the cost of an optimal algorithm that sees the entire input in advance. A 2-competitive algorithm never costs more than twice the best possible offline cost on any input sequence.
- Why does randomization help online algorithms?
- Against an oblivious adversary that fixes the input without seeing the algorithm's random choices, randomization prevents the adversary from tailoring a worst case to the algorithm's behavior, allowing strictly better competitive ratios than any deterministic algorithm can achieve.