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.) Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Selection sort is a sorting algorithm, specifically an in-place comparison sort. ...

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. In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ... A node is a basic unit used to build data structures, such as linked lists and tree data structures. ... Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the...

Online algorithms

The names below are referenced with capital letters since they appear in papers with capital letters. The following are the names of some online algorithms:

• Algorithms for the K-server problem

• BALANCE2
• BALANCE-SLACK
• Double Coverage
• EQUIPOISE
• HANDICAP
• HARMONIC
• RANDOM-SLACK
• Tight Span Algorithm
• Tree Algorithm
• Work Function Algorithm (WFA)

The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). ...

See also

• Adversary Model
• Competitive analysis
• List accessing problem
• Metrical task systems
• Paging Problem
• Real-time computing
• Job shop scheduling

In computer science, an online algorithm measures its competitiveness against different adversary models. ... Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the... It has been suggested that this article or section be merged into cache algorithms. ... Realtime redirects here. ...

References

• Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5. 

Allan Bertram Borodin is a mathematician who has done important work in computational complexity theory. ...

External links

• Bibliography of papers on online algorithms