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. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their 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. 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 neighbors only when it "enters" the node. In Graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes such that the sum of the weights In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects A node is an abstract basic unit used to build linked Data structures such as trees, Linked lists and computer-based representations of graphs 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. 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
Contents |
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)
See also
- Adversary Model
- Competitive analysis
- List accessing problem
- Metrical task systems
- Paging Problem
- Real-time computing
- Job shop scheduling
- Ski rental problem
References
- Borodin, A.; El-Yaniv, R. 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 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 Metrical task systems (MTS are abstract models for competitive analysis of online computation In a Computer Operating system that utilizes Paging for Virtual memory Memory management, page replacement algorithms decide which In Computer science, real-time computing (RTC is the study of hardware and software systems that are subject to a "real-time constraint"—i Job Shop Scheduling is an optimization problem in Computer science in which ideal jobs are assigned to resources at particular times The ski rental problem is the name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one-time cost which eliminates or reduces Allan Bertram Borodin is a Mathematician and Computational theorist who has done important work in Computational complexity theory and Algorithms (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.
External links
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic