- Atlas
- Computer Science
- Online Algorithms
Online Algorithms
An online algorithm is a procedure that must make decisions as data arrives, without knowing what comes next.
7 frameworks, from 1985 to today · Algorithms · Computer Science
Overview
An online algorithm is a procedure that must make decisions as data arrives, without knowing what comes next1. A paging system must evict a page from memory before it knows which pages will be requested; a stock trader must buy or sell before seeing the day's prices; a delivery dispatcher must assign a package to a truck before the rest of the day's orders are known. The field of online algorithms studies what can be guaranteed in such settings: how good a strategy can be when the future is hidden, and what mathematical tools let us prove it1.
What is at stake is the difference between an algorithm that works well on average and one that can be trusted against any sequence of events. The central measure is the competitive ratio: the worst-case ratio between the cost of an online algorithm and the cost of an optimal algorithm that knew the entire input in advance1. An algorithm with competitive ratio c is never more than c times worse than the best possible offline solution, no matter what the input sequence is1. This is a demanding standard, and much of the field's history is the story of finding strategies that meet it, proving that no strategy can do better, and discovering which problems admit good online solutions at all.
Paging and the Origins of Competitive Analysis
The modern field begins with a concrete problem: paging, also called caching. A computer has a fast memory of k pages and a slow memory holding many more. When a requested page is not in fast memory—a cache miss—some page must be evicted to make room2. The question is which page to evict2. The optimal offline strategy, known as Belady's algorithm or the furthest-in-future rule, evicts the page whose next request is furthest away; it was described by Laszlo Belady in 1966. But Belady's rule requires knowing the future, so it cannot be implemented online. It serves as the benchmark against which online strategies are measured.
The first competitive analysis of paging is usually credited to Daniel Sleator and Robert Tarjan, whose 1985 paper "Amortized Efficiency of List Update and Paging Rules" introduced the competitive ratio and analyzed several natural strategies. They showed that the Least Recently Used (LRU) rule—evict the page that has gone longest without being requested—has competitive ratio k, the size of the cache. They also showed that no deterministic online algorithm can do better than k: for any deterministic strategy, an adversary can construct a request sequence that forces it to miss on nearly every request while the optimal offline algorithm misses rarely. This pairing of an upper bound (LRU achieves k) and a matching lower bound (no deterministic algorithm can beat k) became the template for the field.
The idea that an adversary constructs the worst-case input was already implicit in earlier work on list update—the problem of maintaining a linked list where accessing an item costs its position and items can be moved toward the front at no cost. Sleator and Tarjan analyzed the move-to-front heuristic and showed it is 2-competitive, a result that remains one of the cleanest in the field. Their paper made competitive analysis a general framework rather than a collection of ad hoc arguments.
The Potential Function Method
Proving a competitive ratio often requires tracking how an algorithm's state compares to the optimal state over time. The potential function method formalizes this: one defines a nonnegative function of the algorithm's state and the optimal state, and shows that the algorithm's cost plus the change in potential is bounded by a constant times the optimal cost at each step. Summing over the sequence gives the competitive ratio.
The method was used implicitly in Sleator and Tarjan's work and became explicit in the 1990s. A canonical example is the analysis of the work function algorithm for the k-server problem, where the potential measures the difference between the online algorithm's configuration and the optimal offline configuration. The method's power is that it turns a dynamic comparison into a static inequality, and it remains the most common technique for proving upper bounds in online algorithms. Its limitation is that finding the right potential function is an art; there is no general procedure for constructing one.
Metrical Task Systems and the k-Server Problem
In 1988, Allan Borodin, Nathan Linial, and Michael Saks introduced metrical task systems, a general framework for online decision-making. A system has a set of states with a distance metric; at each step a task arrives, and the algorithm must choose a state, paying the cost of moving there plus the cost of serving the task in that state3. Paging is a special case3. The framework made it possible to study online problems abstractly and to ask which metric spaces admit algorithms with bounded competitive ratio.
The k-server problem, introduced by Mark Manasse, Lyle McGeoch, and Daniel Sleator in 1988, is a closely related model: k servers move in a metric space to serve requests, and the cost is the total distance traveled4. The k-server conjecture—that there exists a k-competitive algorithm for every metric space—was posed in that paper and remains one of the field's central open problems4. It was proved for certain metric spaces (lines, trees, and some others) but not in general. The work function algorithm, which at each step moves a server to the requested point in a way that minimizes a combination of past cost and future-looking work, was shown to be (2k−1)-competitive by Yair Bartal and Elias Koutsoupias in the 1990s, and later improved analyses brought the bound closer to k.
Randomization and Adversary Models
Deterministic algorithms face an adversary who knows the algorithm's strategy and can construct a worst-case input5. Randomization changes the game: if the algorithm flips coins, the adversary cannot predict its choices exactly5. The question becomes whether a randomized algorithm can achieve a competitive ratio better than any deterministic one, against an adversary who sees the algorithm's random choices only after the fact5.
The answer depends on the adversary model6. An oblivious adversary must fix the input sequence in advance, without seeing the algorithm's random choices5. An adaptive offline adversary sees the entire sequence of random choices and then chooses the input5. An adaptive online adversary chooses each request after seeing the algorithm's choices so far5. These models give different notions of competitive ratio, and a result by Shai Ben-David, Borodin, and others in the early 1990s showed that for many problems the adaptive offline adversary is equivalent to the deterministic adversary, so randomization offers no advantage against it. Against the oblivious adversary, however, randomization can help: the randomized marking algorithm for paging, analyzed by Fiat, Karp, Luby, McGeoch, Sleator, and Young in 1991, achieves a competitive ratio of 2Hk (where Hk is the k-th harmonic number), exponentially better than the deterministic bound of k. This result established randomization as a central tool and made the choice of adversary model a fundamental modeling decision.
Primal-Dual and LP-Based Methods
Many online problems can be written as linear programs, and the primal-dual method—long used in approximation algorithms—was adapted to the online setting in the late 1990s and 2000s. The idea is to maintain a feasible dual solution online and use it to guide the algorithm's decisions, with the dual objective providing a lower bound on the optimal offline cost. This gives a systematic way to design and analyze competitive algorithms.
A landmark application is the online set cover problem, where elements arrive one at a time and must be covered by sets chosen online. Niv Buchbinder and Joseph Naor, building on earlier work, developed primal-dual algorithms for online set cover and related problems that achieve competitive ratios matching the best known offline approximation ratios up to logarithmic factors. The primal-dual approach also clarified the connection between online algorithms and online learning, particularly the multiplicative weights method, which updates probabilities exponentially in response to costs. This connection, developed in the 2000s, showed that many online algorithms are instances of a general learning framework and opened the field to techniques from convex optimization.
Learning-Augmented Online Algorithms
The classical model assumes the algorithm has no information about the future1. In practice, however, predictions are often available—from machine learning models, historical data, or domain expertise. Learning-augmented online algorithms, also called algorithms with predictions, study what happens when an algorithm is given a prediction about the input and must perform well both when the prediction is accurate and when it is not.
The framework was crystallized in a 2020 paper by Michael Mitzenmacher and Sergei Vassilvitskii on caching with predictions, though related ideas appeared earlier. The key notions are consistency (the competitive ratio when predictions are perfect) and robustness (the competitive ratio when predictions are arbitrarily wrong). A good learning-augmented algorithm achieves consistency better than the classical bound while retaining robustness no worse than the classical bound. For paging, for example, a predictor might supply the next request time for each page; the algorithm can use this to approach Belady's optimal performance when predictions are accurate while falling back to LRU-like guarantees when they are not. The framework has since been applied to scheduling, ski rental, metrical task systems, and many other problems, and it has become one of the most active areas of the field.
The Present
Online algorithms today is a mature field with a recognizable toolkit: competitive analysis as the core framework, potential functions and primal-dual arguments as the main proof techniques, and adversary models as the way to reason about randomization. The classical problems—paging, k-server, metrical task systems, ski rental, online scheduling—remain central because they are clean models of real trade-offs and because several of their basic questions are still open. The k-server conjecture is unresolved4. The exact competitive ratio of randomized algorithms for many problems is unknown. And the learning-augmented framework has reopened classical questions by asking what changes when predictions are available.
The field's influence has spread outward: competitive analysis is now a standard lens in networking, cloud resource allocation, and online marketplaces, and the connection to online learning has made it part of the broader study of decision-making under uncertainty. What began as a way to analyze cache eviction has become a general theory of how to act well when the future is hidden—and of how much better one can do when a little of the future is revealed.
References
- Online algorithm (introduction, Definition), Wikipedia
- Cache replacement policies, Wikipedia
- Metrical task system, Wikipedia
- K-server problem, Wikipedia
- Competitive analysis (online algorithm), Wikipedia
- Adversary model, Wikipedia
The frameworks of Online Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1985-Present
Competitive Analysis
How good can an online algorithm be against the best offline one?
- 1985-Present
Potential Function Method
How can we prove an online algorithm stays close to optimal?
- 1988-Present
- 1988-Present
Metrical task system
Which metric spaces admit bounded-ratio online algorithms?
- 1991-Present
Randomization and Adversary Models
Does randomness help against an adversary?
- 1997-Present
Primal-Dual and LP-Based Methods
Can linear programs guide online decisions?
- 2020-Present
Learning augmented algorithm
How should algorithms use predictions they cannot trust?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
K-Server Problem influenced by Competitive Analysis
The competitive ratio and adversary lower-bound template from Sleator and Tarjan's paging analysis was taken up by Manasse, McGeoch, and Sleator when they introduced the k-server problem and its conjecture in 1988.
Carried by Mark Manasse; Lyle McGeoch; Daniel Sleator.
Randomization and Adversary Models influenced by Competitive Analysis
Randomized competitive analysis extended the deterministic competitive-ratio framework of Sleator and Tarjan to coin-flipping algorithms, with the 1991 randomized marking algorithm for paging analyzed against adversary models.
Carried by Amos Fiat; Richard Karp; Randomized marking algorithm (1991).
Learning augmented algorithm influenced by Competitive Analysis
Learning-augmented algorithms kept the competitive-ratio benchmark of classical online algorithms but added predictions, measuring consistency and robustness relative to that worst-case standard.
Primal-Dual and LP-Based Methods influenced by Competitive Analysis
Primal-dual online algorithms adapted the competitive-ratio goal of the Sleator-Tarjan framework, using dual solutions to certify bounds against the optimal offline cost.
Carried by Niv Buchbinder; Joseph Naor.
Primal-Dual and LP-Based Methods influenced by Randomization and Adversary Models
The connection between primal-dual online algorithms and multiplicative weights drew on randomized online learning and adversary analysis, linking competitive algorithms to exponential-weighting updates.
Carried by Niv Buchbinder; Joseph Naor.
Beyond the field
Where Online Algorithms's ideas came from in other fields, and what they led to there.
K-Server Problem grew out of Online Algorithms and Competitive Analysis in Algorithms
The k-server problem was posed by Manasse, McGeoch and Sleator within the competitive analysis framework, and its study became a central testbed for competitive ratios. It grew directly out of the online algorithms programme.
Carried by Mark Manasse; Lyle McGeoch; Daniel Sleator.
Metrical task system grew out of Online Algorithms and Competitive Analysis in Algorithms
Metrical task systems were introduced by Borodin, Linial and Saks as a generalization within the competitive analysis framework, extending the online competitive-ratio model to a metric state space. The framework grew directly out of online algorithms and competitive analysis.
Carried by Allan Borodin; Nathan Linial; Michael Saks.
Randomization and Adversary Models grew out of Online Algorithms and Competitive Analysis in Algorithms
Randomization and adversary models form a branch of online algorithms and competitive analysis, extending competitive ratios to randomized algorithms against various adversaries. The framework grew directly out of the online competitive-ratio programme.
Primal-Dual and LP-Based Methods grew out of LP rounding and primal-dual in Approximation Algorithms
Primal-dual and LP-based methods for online algorithms grew directly out of the offline LP rounding and primal-dual techniques for approximation algorithms. The online versions adapted the offline primal-dual schema to competitive analysis.
Primal-Dual and LP-Based Methods grew out of Online Algorithms and Competitive Analysis in Algorithms
Primal-dual and LP-based methods are a branch of online algorithms and competitive analysis, providing LP-based proofs of competitive ratios. The framework grew out of the online competitive-ratio programme.
Learning augmented algorithm influenced by Online Algorithms and Competitive Analysis in Algorithms
Learning-augmented algorithms took the competitive-ratio framework and worst-case benchmark of online algorithms and added machine-learned predictions to it. The field's founding papers (e.g. Lykouris and Vassilvitskii on caching with predictions, 2018-2021) explicitly measure performance against the classical competitive analysis baseline.
Carried by Thodoris Lykouris; Sergei Vassilvitskii.
Competitive Analysis influenced by Amortized Analysis in Algorithms
Competitive analysis borrowed the accounting and potential-function style of amortized analysis, treating an online algorithm's cost against an offline optimum much as amortized analysis bounds a sequence of operations. Sleator and Tarjan, who developed both amortized analysis and competitive analysis, carried the technique across.
Carried by Daniel Sleator; Robert Tarjan.
Potential Function Method influenced by Amortized Analysis in Algorithms
The potential function method in online algorithms is a direct adaptation of the potential (banker's) accounting used in amortized analysis. Sleator and Tarjan's amortized potential arguments were taken up as the standard tool for proving competitive ratios.
Carried by Daniel Sleator; Robert Tarjan.
Randomization and Adversary Models influenced Adversarial machine learning in Ai Safety
Adversary models from randomized online algorithms, where an input is chosen by an opponent with knowledge of the algorithm, were taken over as the formal setting for adversarial examples in machine learning.
Primal-Dual and LP-Based Methods influenced by Linear Programming in Mathematical Optimization
LP-based online methods take linear programming duality and the primal-dual schema as their core machinery, adapting them to online settings. Linear programming supplied the duality framework the online analyses use.
K-Server Problem influenced by LP rounding and primal-dual in Approximation Algorithms
LP-based primal-dual and rounding methods from offline approximation were later applied to k-server and related metrical problems to obtain competitive algorithms. The offline LP techniques supplied the analytical machinery.
Metrical task system influenced by Metric space in Point Set Topology
Metrical task systems take the metric space as their state structure, using distances between states to define movement costs. The metric-space concept from topology supplied the formal setting for the model.

Online Algorithms is a planet in Nousfarer
Its city has a tower for each of these 7 frameworks. Land, walk in, and climb one concept at a time.
Land on Online AlgorithmsRelated fields
Fields its ideas are linked to
- Algorithms 7 links
- Approximation Algorithms 2 links
- Ai Safety 1 link
- Mathematical Optimization 1 link
- Point Set Topology 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Online Algorithms sits on the Map of Human Knowledge