Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. (For example, selection sort requires that the entire list is given before it can sort it.)
As an example of the problem consider the problem of finding a shortest path in a finite connected graph when the graph is unknown and the algorithm receives the node neighbours only when it "enters" the node. It is clear that this problem can not be solved optimally without a simple exhaustive search. Thus, new performance measures have to be introduced, such as competitive analysis, which compares the performance of an online algorithm with that of a hypothetical offline algorithm that knows the entire input in advance.
See also
- Adversary (online algorithm)
- List accessing problem
- Metrical task systems
- Paging Problem
- Real-time computing
- K-server problem
References
- Borodin, A. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)