THE LIST UPDATE PROBLEM AND THE RETRIEVAL OF SETS

We consider the list update problem under a sequence of requests for s ets of items, and for this problem we investigate the competitiveness features of two algorithms. We prove that algorithm Move-Set-to-Front (MSF) is (1 + beta)-competitive, where beta is the size of the largest requested set, and that a lower bound is roughly 2. We also provide a n upper bound to the MSF competitive ratio by relating it to the size n of the list, showing that it is (1 + n/4)-competitive in general, an d O(square-root)-competitive with a small constraint to the size of th e requested sets. Moreover, we prove that the randomized algorithm BIT -for-Sets is (1 + 3/4 beta)-competitive against an oblivious adversary . Also, we study two extensions. The first one generalizes the list up date problem under a sequence of requests of sets by considering weigh ted lists, where a weight representing a visiting cost is associated w ith each item. For this case we give a competitiveness result as well. The second one is a variant, where the list is searched to retrieve w hichever element of the currently requested set (the first that can be found in the list). For this problem we provide negative results.