|
Abstract : |
Abstract. We present a randomized on-line algorithm for the list update problem which achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two known algorithms that have different worst-case request sequences. The first is the BIT algorithm that, for each item in the list, alternates between moving it to the front of the list and leaving it at its place after it has been requested. The second is a TIMESTAMP algorithm that moves an item in front of less often requested items within the list. Keywords. On-line algorithms, analysis of algorithms, competitive analysis, list-update. 1. Description of the algorithm The list update problem is one of the first on-line problems that have been studied with respect to competitiveness (see [5] and references). The problem is to maintain an unsorted list of items so that access costs are kept small. An initial list of items is given. A sequence of requests must be served in that order. A request specifies an, |
