Adversary models
An adversary is an entity that gets to choose the request sequence for an algorithm ''ALG''. Depending on whether can be changed based on the strategy of ''ALG'', adversaries are given various powers, and the performance of ''ALG'' is measured against these adversaries. An oblivious adversary has to construct the entire request sequence before running ''ALG'', and pays the optimal offline price, which is compared against An adaptive online adversary gets to make the next request based on the previous results of the online algorithm, but pays for the request optimally and online. An adaptive offline adversary gets to make the next request based on the previous results of the online algorithm, but pays the optimal offline cost.Offline algorithms
Competitive analysis for many list update problems were carried out without any specific knowledge of the exact nature of the optimum offline algorithm (OPT). There exist algorithm runs in O(''n''2''l''(''l''-1)!) time and O(''l''!) space where ''n'' is the length of the request sequence and ''l'' is the length of the list. The best known optimal offline algorithm dependent on request sequence length runs in O(l^2(l−1)!n) time published by Dr Srikrishnan Divakaran in 2014. Paid transpositions are in general necessary for optimum algorithms. Consider a list (''a'',''b'',''c'') where ''a'' is at the head of the list, and a request sequence ''c'',''b'',''c'',''b''. An optimal offline algorithm using only free exchanges would cost 9 (3+3+2+1), whereas an optimal offline algorithm using only paid exchanges would cost 8. So, we cannot get away with just using free transpositions for the optimum offline algorithm. The optimum list update problem was proven to beOnline algorithm
An online algorithm ''ALG'' has a competitive ratio ''c'' if for any input it performs at least as good as ''c'' times worse than OPT. i.e. if there exists an such that for all finite length request sequences , . Online algorithms can either be deterministic or randomized and it turns out that randomization in this case can truly help against oblivious adversaries.Deterministic
Most deterministic algorithms are variants of these three algorithms : ; MTF (Move to front) : After accessing an item move it to the front of the list without changing the order of other items ; TRANS (Transpose) : After accessing an item, transpose it with the immediately preceding item. ; FC (Frequency Count) : For each item maintain a frequency count of the number of accesses to it - when an element is accessed increase its frequency count and reorder the list in the decreasing order of frequencies. Observe that all these use just free transpositions. It turns out that both TRANS and FC are not competitive. In a classic result usingRandomized
Consider the following simple randomized algorithm : ; BIT : For every item in the list, maintain a bit. Initialize all the bits uniformly and randomly to 0 or 1. When an item is accessed, flip the bit, and if it is 1 move it to the front, else don't. This algorithm is barely random - it makes all its random choices in the beginning and not during the run. It turns out that BIT breaks the deterministic bound - it is better than MTF against oblivious adversaries. It is 7/4-competitive. There are other randomized algorithms, like COMB, that perform better than BIT. Boris Teia proved a lower bound of 1.5 for any randomized list update algorithm.Teia, Boris, A lower bound for randomized list update algorithms, Inf. Process. Lett. (1993), pp. 5--9Related problems
The list update problem where elements maybe inserted and deleted is called the dynamic list update problem, as opposed to the static list update problem where only accessing list elements are allowed. The upper bound of holds for the dynamic model as well. There are different cost models as well. In the usual full cost model, an access to an element located at a position ''i'' costs ''i'', but the last comparison is inevitable for any algorithm, i.e. there are ''i-1'' elements standing in the way of ''i''. In the partial cost model, these final comparison costs totaling to the number of elements in the request sequence are ignored. For the costs of paid transpositions other than unity, Pd models are used.See also
*Notes
References
*. * *{{Citation , authorlink = Christoph Ambühl , author = Ambühl, C. , title = Offline list update is np-hard , publisher = Springer , year = 2000 , pages = 42–51 Analysis of algorithms Online algorithms Randomized algorithms