The weighted list update problem and the lazy adversary (Q1208728)

The authors define and study an extension of the list update problem (LUP), namely the weighted list update problem (WLUP). The LUP consists of maintaining a dictionary as an unsorted linear list under a sequence of requests. While processing the sequence, the list may be rearranged in order to minimize the access cost of subseqent operations. For any request, the cost of accessing the searched item depends on its position in the list. In the WLUP any item has an associated cost due for its visit and therefore the cost of searching an item within the list depends on the sum of the costs of the preceding items. Also in this case the problem consists of minimizing the total cost incurred in processing a sequence of requests. This is a typical example of on-line problem, where each request in a sequence has to be processed before the subsequent ones are made known, and some decision taken will affect the cost of answering the subsequent requests. A usual framework to analyze the behavior of heuristics for on- line problems is the technique based on adversaries. An adversary is in charge to generate the sequence of requests in order to maximize the ratio between the cost incurred by the heuristics to be analyzed and the cost of an optimal algorithm to handle the sequence. The heuristic is \(c\)-competitive if this ratio is asymptotically not greater then \(c\). A lazy adversary for an on-line problem is one that moves as few as possible to service requests: in the case of list update problem a lazy adversary does not move anything. The authors consider heuristics for the WLUP and show that the well known Move-To-Front (after accessing an item, move it to the front of the list without changing the relative ordering of the other items), 2-competitive for the LUP, is not \(c\)-competitive against a lazy adversary by any constant factor in the weighted case. In contrast, the authors propose two heuristics for this problem, both derived from Move-To-Front: the Counting Move-To-Front, which is a deterministic heuristic which uses \(n\) real counters (one counter per item) in order to decide whether moving to the front the accessed items, and the Random Move-To-Front, which is a randomized heuristic, obtained by CMTF by substituting counters by biased coins. Both are shown to be 2-competitive against a lazy adversary. Moreover the authors define and study the Tree Update Problem, where items are to be found in a tree instead of in a sequential list. The tree is represented by means of lists of successors and is searched by a leftist depth first search. The only possible update operation consists in rearranging the list of children of the vertices. It is shown that by weighing each vertex by the size of its subtree, it is possible to handle the list of the children of any vertex by using any weighted list updated heuristic in order to reduce the overall cost of processing a sequence of searchers over the tree. This allows the following result: given a heuristic for the WLUP \(c\)-competitive against an adversary, it is possible to devise a heuristic for the Tree Update Problem \(c\)-competitive against the same adversary. For example AND-OR trees, problem solving and diagnosis are some of the areas which could exploit efficient solutions for the WLUP.