Online algorithm
From Wikipedia, the free encyclopedia
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 be 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 neighbors 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.
Contents |
[edit] 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)
[edit] See also
- Adversary Model
- Competitive analysis
- List accessing problem
- Metrical task systems
- Paging Problem
- Real-time computing
- Job shop scheduling
- Ski rental problem
[edit] References
- Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.
