Online algorithm

An online algorithm is a method of solving problems where not all input data are available at the beginning of the calculation process.

In many algorithmically solvable problems in computer science, the full input data before execution of each algorithm are known. Using these data, a solution is calculated and output. Such problems are called off-line problems.

In on-line problems, however, the input data at the time of execution of the algorithm are updated continuously. In other words: Certain information is only available if certain other data is already available - and can also only be taken into account to solve the problem. The algorithm can not make any assumptions about the complete data.

It is essential that the algorithm already have to make decisions before the data has been submitted., Usually from several times. These decisions may be " in arrears " turn out to be unhappy or bad, but either no longer or redeemed only with additional cost.

An example of an online problem is the search for a shortest path in a graph, where the graph is initially unknown, and will receive information about the nodes and edges only at the " entering " of a node. An optimal solution can be achieved only with complete information, which requires visiting all nodes.

Very similar is the movement of an autonomous robot in an unexplored environment or the navigation of Spiders in the World Wide Web.

In some cases, applications of machine learning will also work online; the system learns during his "work".

From a theoretical point of view are examined by the so-called competitivity Online algorithms. This is essentially the ratio of solution cost of the online algorithm for which an optimal solution (which could be calculated with prior knowledge of the complete data ) in the worst case (over all possible sequences of gradual incoming information ). Depending on the problem are different grades accessible here. This notation is closely related to the approximation ratio of approximation algorithms.