List Update Problem
To illustrate competitive analysis, consider the problem
of maintaining a list under accesses:
- Cost of accessing the ith element: i.
- Cost of swapping neighbors: 1.
Some Heuristics to consider:
- Decreasing Frequency (DF)
- Transpose (T)
- Move-To-Front (MTF)
Theorem:
The MTF algorithm is 4-competitive.
DF and T are not competitive.
Example:
My wallet.
[back]
[next]
[home]