Information about 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.
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.
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
References
- Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.
External links
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
..... Click the link for more information.
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has Θ(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
..... Click the link for more information.
..... Click the link for more information.
In graph theory, the 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. An example is finding the quickest way to get from one location to another on a road map; in this case, the
..... Click the link for more information.
..... Click the link for more information.
graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.
..... Click the link for more information.
A node is an abstract basic unit used to build linked data structures, such as linked lists and trees, and computer-based representation of graphs. Nodes contain data and/or links to other nodes. Links between nodes are often implemented by pointers or references.
..... Click the link for more information.
..... Click the link for more information.
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
..... Click the link for more information.
..... Click the link for more information.
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).
..... Click the link for more information.
..... Click the link for more information.
adversary models. For deterministic algorithms, the adversary is the same, the adaptive offline adversary. For randomized online algorithms competitiveness can depend upon the adversary model used.
..... Click the link for more information.
..... Click the link for more information.
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
..... Click the link for more information.
..... Click the link for more information.
Metrical task systems (MTS) are abstract models for competitive analysis of online computation. Metrical task systems play roles in online problems such as paging, list accessing, and the k-server problem (in finite spaces).
..... Click the link for more information.
..... Click the link for more information.
real-time computing (RToC) is the study of hardware and software systems which are subject to a "real-time constraint"—i.e., operational deadlines from event to system response.
..... Click the link for more information.
..... Click the link for more information.
Allan Bertram Borodin is a mathematician and computational theorist who has done important work in computational complexity theory.
He received his Ph.D. in computer science from Cornell University in 1969 and is a professor at the University of Toronto.
..... Click the link for more information.
He received his Ph.D. in computer science from Cornell University in 1969 and is a professor at the University of Toronto.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
