Competitive analysis (online algorithm): Difference between revisions

Revision as of 23:48, 17 September 2010

Revision as of 16:28, 19 October 2010

Line 9:

The classic on-line problem first analysed with competitive analysis {{harv|Sleator|Tarjan|1985}} is the ''List Update problem'': Given a list of items and a sequence of requests for the various items, minimize the cost of accessing the list where the elements closer to the front of the list cost less to access. (Typically, the cost of accessing an item is equal to its position in the list.) After an access, the list may be rearranged. Most rearrangements have a cost. The ''Move-To-Front algorithm'' simply moves the requested item to the front after the access, at no cost. The ''Transpose algorithm'' swaps the accessed item with the item immediately before it, also at no cost. Classical methods of analysis showed that Transpose is optimal in certain contexts. In practice, Move-To-Front performed much better. Competitive analysis was used to show that an adversary can make Transpose perform arbitrarily badly compared to an optimal algorithm, whereas Move-To-Front can never be made to incur more than twice the cost of an optimal algorithm.

In the case of online requests from a server, competitive algorithms are used to overcome uncertainties about the future. That is, the algorithm does not "know" the future, while the imaginery adversary (the "competitor") "knows. Similarly, copetitivecompetitive algorithms were developed for distributed systems, where the algorithm has to react to a request arriving at one ___location, without "knowing" what has just happened in a remote ___location. This setting was presented in

{{harv|Awerbuch|Kutten|Peleg|1992}}.