Editing Online algorithm (section)

== Online problems ==
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]].

There are many formal problems that offer more than one ''online algorithm'' as solution:
* [[K-server problem|''k''-server problem]]
* [[Job shop scheduling|Job shop scheduling problem]]
* [[List update problem]]
* [[Bandit problem]]
* [[Secretary problem]]
* [[Search games]]
* [[Ski rental problem]]
* [[Linear search problem]]
* Portfolio selection problem<ref name=doc16>{{cite book|last1=Dochow|first1=Robert|title=Online Algorithms for the Portfolio Selection Problem|date=2016|publisher=Springer Gabler|url=https://www.springer.com/de/book/9783658135270}}</ref>