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

still a working view ended · each leads to its entry below

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

  1. Online algorithm (introduction, Definition), Wikipedia
  2. Cache replacement policies, Wikipedia
  3. Metrical task system, Wikipedia
  4. K-server problem, Wikipedia
  5. Competitive analysis (online algorithm), Wikipedia
  6. 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.

  1. 1985-Present

    Competitive Analysis

    How good can an online algorithm be against the best offline one?

    Fly to its tower in Nousfarer

  2. 1985-Present

    Potential Function Method

    How can we prove an online algorithm stays close to optimal?

    Fly to its tower in Nousfarer

  3. 1988-Present

    K-Server Problem

    Can k servers match the best offline movement?

    Fly to its tower in Nousfarer

  4. 1988-Present

    Metrical task system

    Which metric spaces admit bounded-ratio online algorithms?

    Fly to its tower in Nousfarer

  5. 1991-Present

    Randomization and Adversary Models

    Does randomness help against an adversary?

    Fly to its tower in Nousfarer

  6. 1997-Present

    Primal-Dual and LP-Based Methods

    Can linear programs guide online decisions?

    Fly to its tower in Nousfarer

  7. 2020-Present

    Learning augmented algorithm

    How should algorithms use predictions they cannot trust?

    Fly to its tower in Nousfarer

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.

Competitive AnalysisPotential Function MethodK-Server ProblemMetrical task systemRandomization and Adversary ModelsPrimal-Dual and LP-Based MethodsLearning augmented algorithm

Beyond the field

Where Online Algorithms's ideas came from in other fields, and what they led to there.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Online Algorithms sits on the Map of Human Knowledge