Encyclopedia > Online computations and algorithms

  Article Content

Online computations and algorithms

A common approach in computer science to problem solving is offline computation. This means that the whole problem data is given from the beginning and one is required to output an answer which solves the problem in hand.

Other problems, however, are online. This means the whole dataset is not available and the algorithm receives the information piece by piece. This domain is called online algorithms and computation. It is often studied in machine learning.

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Quioque, New York

... or more races. 14.38% of the population are Hispanic or Latino of any race. There are 336 households out of which 28.9% have children under the age of 18 living with them, ...

This page was created in 25.2 ms