An online algorithm is an algorithm that processes an input sequence as its elements arrive, making each required decision without knowing the future elements. Earlier decisions either cannot be changed or incur a cost when changed. In contrast, an offline algorithm knows the complete input before making its decisions (Borodin and El-Yaniv 1998).

The distinction concerns access to information rather than running time or access to a computer network. For example, in the k-server problem, an online algorithm must choose which server to move to the current request before learning the next request. A server movement that is inexpensive now may make a later request expensive to serve.

The competitive ratio compares the cost of an online algorithm with the minimum cost of an offline algorithm on the same input sequence. This comparison separates the cost of lacking future information from the difficulty of computing an optimal solution. The work function algorithm uses optimal offline costs for the revealed prefix to guide its online decisions.

See also

Algorithm, Competitive Ratio, k-Server Problem, Matroid Prophet Inequality, Prophet Inequality, Work Function Algorithm

Explore with Wolfram|Alpha

References

Borodin, A. and El-Yaniv, R. Online Computation and Competitive Analysis. Cambridge, England: Cambridge University Press, 1998.

Cite this as:

Weisstein, Eric W. "Online Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OnlineAlgorithm.html

Subject classifications