×

The weighted list update problem and the lazy adversary. (English) Zbl 0779.68079

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.
Reviewer: Fabrizio d’Amore

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Y. Azar and U. Nanni, personal communication, 1991.; Y. Azar and U. Nanni, personal communication, 1991.
[2] Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A., On the power of randomization in on-line algorithms, Proc. 20th ACM Ann. Symp. on Theory of Computing, 379-386 (1990)
[3] Bentley, J. L.; McGeogh, C., Amortized analyses of self-organizing sequential search heuristics, Comm. ACM, 28, 4, 404-411 (1985)
[4] Bitner, J. R., Heuristics that dynamically organize data structures, SIAM J. Comput., 8, 1, 82-110 (1979) · Zbl 0395.68022
[5] Borodin, A.; Irani, S.; Raghavan, P.; Schieber, B., Competitive paging with locality of reference, Proc. 21st ACM Ann. Symp. on Theory of Computing, 249-259 (1991)
[6] d’Amore, F.; Nanni, U.; Marchetti-Spaccamela, A., Robust algorithms for diagnosis, (Tech. Report (1991), Dipartimento di Informatica e Sistemistica, Univ. of Roma “La Sapienza”)
[7] Fiat, A.; Karp, R. M.; Luby, M.; McGeoch, L. A.; Sleator, D. D.; Young, N. E., Competitive paging algorithms, J. Algorithms, 12, 685-699 (1991) · Zbl 0753.68018
[8] Gnesi, S.; Montanari, U.; Martelli, A., Dynamic programming as graph searching: An algebraic approach, J. ACM, 28, 737-751 (1981) · Zbl 0471.90092
[9] Hester, J. H.; Hirschberg, D. S., Self-organizing linear search, ACM Comput. Surveys, 17, 3, 295-311 (1985)
[10] Hofri and H. Shachnai, M., On the limited utility of auxiliary information in the list update problem (1991), manuscript
[11] Irani, S., Two results on the list update problem, (Technical Report TR-90-037 (1990), Computer Science Division, Univ. of California: Computer Science Division, Univ. of California Berkeley, CA) · Zbl 0737.68043
[12] Irani, S.; Karlin, A. R.; Phillips, S., Strongly competitive algorithms for paging with locality of reference, Proc. 3rd ACM-SIAM Ann. Symp. on Discrete Algorithms, 228-236 (1992), Orlando, FL · Zbl 0834.68049
[13] Irani, S.; Reingold, N.; Westbrook, J.; Sleator, D. D., Randomized competitive algorithms for the list update problem, Proc. 2nd ACM-SIAM Ann. Symp. on Discrete Algorithms, 251-260 (1991), San Francisco, CA · Zbl 0800.68503
[14] Karlin, A. R.; Manasse, M. S.; Rudolph, L.; Sleator, D. D., Competitive snoopy catching, Algorithmica, 3, 1, 79-119 (1988) · Zbl 0645.68034
[15] R. Karp and P. Raghavan, unpublished result, 1990.; R. Karp and P. Raghavan, unpublished result, 1990.
[16] Manasse, M. S.; McGeoch, L. A.; Sleator, D. D., Competitive algorithms for on-line problems, Proc. 18th ACM Ann. Symp. on Theory of Computing, 322-333 (1988)
[17] Manasse, M. S.; McGeoch, L. A.; Sleator, D. D., Competitive algorithms for server problems, J. Algorithms, 11, 2, 208-230 (1990) · Zbl 0705.68023
[18] Nilsson, N. J., Principles of Artificial Intelligence (1982), Springer: Springer Berlin · Zbl 0474.68094
[19] Reiter, R., A theory of diagnosis from first principles, Artificial Intelligence, 32, 57-95 (1987) · Zbl 0643.68122
[20] Rivest, R., On self-organizing sequential search heuristics, Comm. ACM, 19, 2, 63-67 (1976) · Zbl 0317.68025
[21] Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Comm. ACM, 28, 2, 202-208 (1985)
[22] Tarjan, R. E., Amortized computational complexity, SIAM J. Alg. Disc. Meth., 6, 2, 306-318 (1985) · Zbl 0599.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.