The Weighted List Update Problem and the Lazy Adversary

The "List Update Problem" consists in maintaining a dictionary as an unsorted linear list. Any request specifies an item to be found by sequential scanning through the list. After an item has been found, the list may be rearranged in order to reduce the cost of processing a "sequence" of requests. Several kinds of adversaries can be considered to analyze the behavior of heuristics for this problem. The "Move-to-Front" (MTF) heuristic is 2-competitive against a "strong" adversary, matching the deterministic lower bound for this problem [21]. But, for this problem, moving elements does not help the adversary. A "lazy" adversary has the limitation that he can use only a static arrangement of the list to process (off-line) the sequence of requests: still, no algorithm can be better than 2-competitive against the lazy adversary [3]. In this paper we consider the "Weighted List Update Problem" (WLUP) where the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any consent factor for this problem against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: "Random Move-to- Front" is randomized and uses biased coins; "Counting Move-to- Front" is deterministic, and replaces coins by counters. Both are shown to be 2-competitive against a lazy adversary. This is optimal for the deterministic case.We apply this approach for searching items in a tree, proving that any "c"-competitive heuristic for the weighted list update problem provides a "c"-competitive heuristic for the "Tree Update Problem".

ICSI Technical Report TR-92-011

Technical Report