Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Online_algorithm> ?p ?o. }
Showing items 1 to 39 of
39
with 100 items per page.
- Online_algorithm abstract "In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, 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, while insertion sort doesn't.)Because it does not know the whole input, an online algorithm is forced to make decisions that may later turn out not to be optimal, and the study of online algorithms has focused on the quality of decision-making that is possible in this setting. Competitive analysis formalizes this idea by comparing the relative performance of an online and offline algorithm for the same problem instance. Specifically, the competitive ratio of an algorithm, is defined as the worst-case ratio of its cost divided by the optimal cost, over all possible inputs . The competitive ratio of an online problem is the best competitive ratio achieved by an online algorithm. Intuitively, the competitive ratio of an algorithm gives a measure on the quality of solutions produced by this algorithm, while the competitive ratio of a problem shows the importance of knowing the future for this problem. For other points of view on online inputs to algorithms, see streaming algorithm (focusing on the amount of memory needed to accurately represent past inputs), dynamic algorithm (focusing on the time complexity of maintaining solutions to problems with online inputs) and online machine learning.A problem exemplifying the concepts of online algorithms is the Canadian Traveller Problem. The goal of this problem is to minimize the cost of reaching a target in a weighted graph where some of the edges are unreliable and may have been removed from the graph. However, that an edge has been removed (failed) is only revealed to the traveller when she/he reaches one of the edge's endpoints. The worst case for this problem is simply that all of the unreliable edges fail and the problem reduces to the usual Shortest Path Problem. An alternative analysis of the problem can be made with the help of competitive analysis. For this method of analysis, the offline algorithm knows in advance which edges will fail and the goal is to minimize the ratio between the online and offline algorithms' performance. This problem is PSPACE-complete.".
- Online_algorithm wikiPageExternalLink book.html.
- Online_algorithm wikiPageExternalLink online.bib.
- Online_algorithm wikiPageID "22716".
- Online_algorithm wikiPageRevisionID "597686625".
- Online_algorithm hasPhotoCollection Online_algorithm.
- Online_algorithm subject Category:Online_algorithms.
- Online_algorithm type Abstraction100002137.
- Online_algorithm type Act100030358.
- Online_algorithm type Activity100407535.
- Online_algorithm type Algorithm105847438.
- Online_algorithm type Event100029378.
- Online_algorithm type OnlineAlgorithms.
- Online_algorithm type Procedure101023820.
- Online_algorithm type PsychologicalFeature100023100.
- Online_algorithm type Rule105846932.
- Online_algorithm type YagoPermanentlyLocatedEntity.
- Online_algorithm comment "In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, 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.".
- Online_algorithm label "Algorithme d'apprentissage incrémental".
- Online_algorithm label "Algoritmo online".
- Online_algorithm label "Algorytm online".
- Online_algorithm label "Online algorithm".
- Online_algorithm label "Online-Algorithmus".
- Online_algorithm label "Online-algoritme".
- Online_algorithm label "オンラインアルゴリズム".
- Online_algorithm label "線上演算法".
- Online_algorithm sameAs Online-Algorithmus.
- Online_algorithm sameAs Algorithme_d'apprentissage_incrémental.
- Online_algorithm sameAs Algoritmo_online.
- Online_algorithm sameAs オンラインアルゴリズム.
- Online_algorithm sameAs 온라인_알고리즘.
- Online_algorithm sameAs Online-algoritme.
- Online_algorithm sameAs Algorytm_online.
- Online_algorithm sameAs m.05ph2.
- Online_algorithm sameAs Q786431.
- Online_algorithm sameAs Q786431.
- Online_algorithm sameAs Online_algorithm.
- Online_algorithm wasDerivedFrom Online_algorithm?oldid=597686625.
- Online_algorithm isPrimaryTopicOf Online_algorithm.