Loading field map
Online algorithms are a branch of algorithm design and analysis concerned with problems in which an algorithm must make decisions without knowing the full input in advance. The input arrives piece by piece, and the algorithm must produce a partial output or take an irrevocable action after each piece arrives, before seeing the rest of the input. The central challenge is to make good decisions under this enforced ignorance, and the central question is how well an online algorithm can perform compared to a hypothetical offline algorithm that sees the entire input from the start.
To understand online algorithms, it helps to contrast them with the classical model of computation. In the standard model, an algorithm receives the entire input, processes it, and produces an output. The algorithm's quality is judged by its running time and the correctness of its output. Online algorithms abandon this setup. The input is a sequence of requests or events, and the algorithm must respond to each one as it arrives. The response may be a choice among options, an allocation of resources, or a decision to accept or reject a request. Crucially, the decision is final; it cannot be revised when future requests arrive.
This model is not an artificial contrivance. Many real-world problems have this structure: a ski rental decision, where you must decide whether to rent or buy equipment without knowing how many more times you will ski; a paging system in an operating system, which must decide which memory pages to keep in fast cache without knowing which pages future programs will request; an online auction, where a seller must decide whether to accept a bid without knowing what future bids will be; or a routing system that must send a packet along a path without knowing future congestion.
The standard framework for analyzing online algorithms is competitive analysis, introduced in the mid-1980s. The idea is to compare the performance of an online algorithm against that of an optimal offline algorithm—one that knows the entire request sequence in advance. For a minimization problem, an online algorithm is said to be c-competitive if, for every possible input sequence, the cost incurred by the online algorithm is at most \( c \) times the cost incurred by the optimal offline algorithm, plus possibly a constant. The competitive ratio is the infimum over all such \( c \). For maximization problems, the definition is inverted: the online algorithm's gain must be at least \( 1/c \) times the offline optimum. The competitive ratio is a worst-case guarantee; it holds for every input sequence, not just on average.
Competitive analysis is a deliberately pessimistic measure. It assumes an adversary constructs the input sequence, and the adversary knows the algorithm's strategy. This makes the analysis tractable and yields strong guarantees, but it also means that competitive ratios can be discouragingly large. A classic example is the paging problem, where the optimal competitive ratio is the size of the cache, meaning that an online algorithm can be forced to perform as badly as if it had no cache at all. This worst-case perspective has been criticized as too harsh, and several refinements have been proposed, but competitive analysis remains the foundational tool of the field.
The intellectual roots of online algorithms lie in the study of online problems in operations research and decision theory, where sequential decision-making under uncertainty had long been studied. However, the modern field took shape in the 1980s when computer scientists began to apply worst-case analysis to these sequential decision problems. The paging problem was a key early example, and the realization that simple deterministic strategies like "evict the least recently used page" have provable guarantees, while other natural strategies fail badly, helped establish the value of the competitive analysis framework.
A landmark development was the discovery that randomization can help. A randomized online algorithm makes decisions using random bits, and its competitive ratio is defined with respect to the expected cost. For paging, randomized algorithms achieve a competitive ratio that is logarithmic in the cache size, which is strictly better than the best possible deterministic ratio. This was a surprising and influential result, showing that the distinction between deterministic and randomized algorithms is fundamental in the online setting, much as it is in distributed computing and other areas.
Another important thread was the study of lower bounds. A lower bound in competitive analysis is a statement that no online algorithm—deterministic or randomized—can achieve a competitive ratio better than some value. These results are often proved using adversary arguments, where the adversary adaptively constructs the input sequence based on the algorithm's behavior. Lower bounds are essential because they tell us when an algorithm is optimal and when further improvement is impossible.
The field expanded rapidly in the 1990s and 2000s, with researchers applying the online framework to a wide range of problems: load balancing, where jobs arrive over time and must be assigned to machines; scheduling, where jobs with deadlines must be processed; the k-server problem, where a set of servers must move to serve requests at points in a metric space; and various network problems, such as routing and caching. Each of these problems has its own structure, and the competitive ratios achievable depend on that structure in subtle ways.
The field is not organized into a small number of rival schools with mutually exclusive doctrines. Rather, it is characterized by a set of overlapping techniques and perspectives that researchers combine as needed. Still, several broad approaches can be distinguished.
The earliest and most basic approach is to design deterministic algorithms and prove their competitive ratios directly. The standard proof technique is the potential function method. The algorithm maintains a potential function—a numerical value that depends on the current state of the algorithm and the state of the optimal offline algorithm. The proof shows that whenever the online algorithm incurs cost, the potential changes in a way that bounds the total cost. This method is powerful and general, and it underlies many of the classic results in the field.
For example, in the paging problem, the "least recently used" (LRU) algorithm is \( k \)-competitive, where \( k \) is the cache size. The proof uses a potential function that measures the distance between the set of pages in the online cache and the set of pages in the offline cache. The potential function method is not just a proof technique; it also guides the design of algorithms. Many online algorithms are designed by first constructing a potential function that captures the trade-off between immediate cost and future flexibility.
Randomized online algorithms form a second major approach. The motivation is that randomization can "confuse" the adversary. If the adversary does not know the algorithm's random choices, it cannot tailor the input sequence to force the worst case. The standard tool for analyzing randomized algorithms is Yao's principle, which provides a way to prove lower bounds. Yao's principle states that the expected competitive ratio of the best randomized algorithm against any adversary is equal to the competitive ratio of the best deterministic algorithm against a distribution over input sequences. This duality is useful because it allows researchers to prove lower bounds on randomized algorithms by constructing distributions over inputs that are hard for any deterministic algorithm.
Randomized algorithms have been particularly successful for problems where the deterministic competitive ratio is large. The paging problem is the canonical example, but randomization has also been applied to load balancing, the k-server problem, and many others. The relationship between deterministic and randomized algorithms is subtle: randomization sometimes helps dramatically, sometimes helps only marginally, and sometimes does not help at all. Understanding when randomization helps is an active research question.
The k-server problem deserves special mention because it has served as a unifying framework for much of the field. In this problem, there are \( k \) servers located at points in a metric space. Requests arrive one at a time, each at a point in the space, and the algorithm must move one of its servers to the request point. The cost is the total distance traveled. The problem generalizes paging (where the metric space is the set of pages, and moving a server corresponds to fetching a page into cache) and many other problems.
The k-server problem was conjectured to have a competitive ratio of \( k \) for any metric space, and this conjecture drove research for many years. The conjecture was eventually resolved in the affirmative for deterministic algorithms, but the proof is highly nonconstructive and does not yield a practical algorithm. The problem remains a rich source of techniques and open questions, and it has connections to other areas of computer science, including metric embeddings and online learning.
A more recent development is the use of work-function and primal-dual methods. The work-function algorithm maintains a function that records, for each possible state of the system, the minimum cost of serving the requests seen so far and ending in that state. The algorithm then makes decisions that are greedy with respect to this function. This approach has been used to design algorithms for the k-server problem and related problems, and it has connections to dynamic programming and to the theory of metrical task systems.
The primal-dual method, borrowed from linear programming, has been applied to online problems by maintaining a dual solution alongside the primal solution. The method is particularly useful for problems with a linear programming formulation, such as caching, routing, and covering problems. The primal-dual approach has led to algorithms with improved competitive ratios for several problems, and it has also provided a unified way to think about online problems that have a combinatorial optimization structure.
A significant recent trend is the move beyond worst-case competitive analysis. The worst-case model assumes an adversary that knows the algorithm and tries to maximize the competitive ratio. In practice, however, input sequences are often not adversarial; they may have structure that can be exploited. Several alternative models have been proposed.
Diffuse adversaries assume that the adversary is restricted in the sequences it can generate, for example by a probability distribution or by a bound on the total variation between consecutive requests. Access graph models assume that the request sequence respects a graph structure, such as a locality of reference in paging. Smoothed analysis assumes that the input is a worst-case sequence perturbed by random noise. These models are not replacements for competitive analysis but rather refinements that aim to give more realistic performance guarantees.
Another important alternative is the competitive ratio with advice, where the online algorithm is allowed to receive a small amount of information about the future, and the question is how much advice is needed to achieve a given competitive ratio. This model interpolates between the online and offline settings and has connections to communication complexity and to the theory of automata.
The field of online algorithms is mature but active. The core techniques—potential functions, Yao's principle, work functions, primal-dual methods—are well understood and are taught as standard tools. The field has expanded to include a wide range of problems, and the connections to other areas of computer science have deepened.
One important connection is to online learning, a subfield of machine learning. In online learning, an algorithm makes predictions and receives feedback, and the goal is to minimize regret—the difference between the algorithm's total loss and the loss of the best fixed strategy in hindsight. The mathematical structure of online learning is closely related to that of online algorithms, and techniques from one field have been successfully transferred to the other. The relationship is not one of identity, however: online learning typically assumes that the input is generated by a stochastic process or by an adversary with limited power, while online algorithms traditionally assume a fully adversarial input.
Another connection is to data structures. Many data structure problems, such as the dynamic maintenance of a binary search tree, have an online flavor: the sequence of operations is not known in advance, and the data structure must respond to each operation as it arrives. The competitive analysis of data structures, such as the dynamic optimality conjecture for binary search trees, is an active area of research that draws on the techniques of online algorithms.
The field also continues to find new applications. Online algorithms are used in cloud computing for resource allocation, in ad auctions for bid optimization, in network routing for congestion control, and in many other settings where decisions must be made in real time. The competitive analysis framework provides a principled way to reason about these problems, even when the specific algorithms used in practice are heuristic.
A notable feature of the current landscape is the coexistence of multiple models and measures. Competitive analysis remains the default, but it is no longer the only game in town. Researchers routinely consider randomized versus deterministic algorithms, adversarial versus stochastic inputs, worst-case versus average-case guarantees, and the role of advice or predictions. This pluralism is a sign of a healthy field: it reflects the recognition that no single measure captures all the trade-offs that arise in real-world online decision-making.
The field also has a clear set of open problems. The most famous is the k-server conjecture, which was resolved for deterministic algorithms but remains open for randomized algorithms in general metric spaces. Other open problems concern the exact competitive ratios for specific problems, the power of randomization, and the design of algorithms that are simultaneously competitive against multiple measures. These open problems are not merely technical curiosities; they represent fundamental gaps in our understanding of how to make good decisions under uncertainty.
In summary, online algorithms is the study of decision-making under partial information, where the quality of an algorithm is measured by comparing its performance to that of a clairvoyant offline algorithm. The field has developed a rich set of techniques—potential functions, randomization, primal-dual methods, and others—and it has established deep connections to optimization, learning, and data structures. Its central questions—how much performance is lost due to ignorance of the future, and how can that loss be minimized—are fundamental to computer science and to any domain that involves sequential decisions under uncertainty.