An on-line algorithm for the list update problem has been proposed and is shown to be 2-competitive under any sequence of access requests. The simpler version of the algorithm can be easily and efficiently implemented. Further, using this algorithm as a procedure in data compression technique it is possible to obtain better compression ratio than other known algorithms.
展开▼
