Loading field map
An online algorithm must make decisions without knowing the future. In many real-world settings—scheduling jobs on a server, managing a cache, routing data through a network, or buying and selling stock—input arrives piece by piece, and each decision is irreversible or costly to undo. The central tension in online algorithms is therefore between the need to act immediately and the desire to act optimally. How can we measure the quality of an algorithm that never sees the full picture? And how can we design algorithms that perform well despite this blindness?
The first systematic answer came in 1985, when Daniel Sleator and Robert Tarjan introduced competitive analysis. Their idea was to compare an online algorithm's performance against that of an optimal offline algorithm—a hypothetical algorithm that knows the entire input sequence in advance. An online algorithm is said to be c-competitive if its cost on every input sequence is at most c times the offline optimum's cost, plus a constant. This ratio, the competitive ratio, became the standard metric for online algorithms.
Competitive analysis replaced earlier ad-hoc comparisons by providing a clean, worst-case guarantee. For example, the classic "ski rental" problem—where you must decide whether to rent or buy skis without knowing how many times you will ski—has a simple 2-competitive deterministic algorithm. The framework spread quickly to problems in data structures (list update, self-organizing lists), operating systems (paging, caching), and finance (online portfolio selection).
Yet competitive analysis also has limitations. Its worst-case orientation can be overly pessimistic: an algorithm that is optimal in the worst case may perform poorly on typical inputs, and vice versa. Moreover, for some problems, no deterministic algorithm can achieve a bounded competitive ratio, forcing researchers to look for alternative measures.
Randomized online algorithms emerged in the early 1990s as a direct response to the limitations of deterministic competitive analysis. By introducing randomness into their decisions, these algorithms can achieve better expected competitive ratios than any deterministic algorithm can guarantee. For instance, the randomized algorithm for the ski rental problem achieves an expected competitive ratio of e/(e-1) ≈ 1.58, strictly better than the deterministic bound of 2.
Randomization does not abandon the competitive analysis framework; rather, it extends it. The adversary is now assumed to be oblivious—it must choose the input sequence without knowing the algorithm's random choices. This shift from deterministic to randomized competitive analysis opened up new problems and tighter bounds. The framework remains active today, especially in problems where deterministic lower bounds are severe, such as online matching and online load balancing.
By the early 2000s, researchers began asking a different question: how much information about the future does an online algorithm actually need to achieve a given competitive ratio? This question gave rise to advice complexity, introduced by J. Hromkovič, R. Královič, and colleagues around 2003. In this model, the algorithm can consult a tape of advice bits—provided by an all-knowing oracle—before or during its execution. The goal is to determine the minimum number of advice bits required to achieve a certain competitive ratio.
Advice complexity does not replace competitive analysis; it complements it by providing a finer-grained understanding of the trade-off between information and performance. For example, a single bit of advice can sometimes reduce the competitive ratio from unbounded to constant. The framework has been applied to paging, scheduling, and graph problems, and it remains an active area of research, especially in exploring the boundary between online and offline computation.
The most recent major framework, learning-augmented online algorithms, emerged around 2018 from the work of Thodoris Lykouris and Sergei Vassilvitskii, among others. The key insight is that in many practical settings, machine learning models can provide predictions about future inputs—for example, predicting the next page request in a cache or the next job arrival in a scheduler. Learning-augmented algorithms incorporate these predictions while still maintaining worst-case guarantees when the predictions are inaccurate.
This framework addresses a long-standing tension between worst-case competitive analysis and average-case or heuristic approaches. Unlike pure competitive analysis, which assumes no knowledge of the future, learning-augmented algorithms can exploit predictions to achieve better-than-worst-case performance on typical inputs. Unlike pure machine learning, they do not fail catastrophically when predictions are wrong. The framework has produced algorithms with strong "consistency" (good performance when predictions are accurate) and "robustness" (bounded performance when predictions are poor).
Today, all four frameworks remain active and are often used in combination. Competitive analysis remains the default baseline: any new online algorithm is expected to state its competitive ratio. Randomized online algorithms are the standard tool when deterministic bounds are too pessimistic. Advice complexity provides a theoretical lens for understanding the information requirements of online problems. Learning-augmented algorithms are the fastest-growing area, driven by the practical success of machine learning.
There is broad agreement that no single framework is sufficient. Competitive analysis is too pessimistic for many applications; randomized algorithms require careful adversarial modeling; advice complexity is largely theoretical; learning-augmented algorithms depend on the quality of predictions. The main disagreement concerns how to balance worst-case guarantees with average-case performance. Some researchers argue that the field should move toward more realistic models that incorporate prediction quality, while others maintain that worst-case guarantees are essential for rigorous algorithm design.
Online algorithms share deep connections with approximation algorithms and randomized algorithms. Approximation algorithms also deal with NP-hard problems, but they assume the entire input is known in advance; online algorithms face the additional challenge of incomplete information. Randomized algorithms provide tools for online algorithms, especially in breaking deterministic lower bounds. The learning-augmented framework also draws on ideas from streaming algorithms, where data arrives sequentially and memory is limited, though streaming algorithms focus on space constraints rather than future uncertainty.