The list update problem and the retrieval of sets

AbstractWe consider the list update problem under a sequence of requests for sets 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 + β)-competitive, where β is the size of the largest requested set, and that a lower bound is roughly 2. We also provide an 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, and O(n)-competitive with a small constraint to the size of the requested sets.Moreover, we prove that the randomized algorithm BIT-for-Sets is (1 + 34β)-competitive against an oblivious adversary.Also, we study two extensions. The first one generalizes the list update problem under a sequence of requests of sets by considering weighted lists, where a weight representing a visiting cost is associated with 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 whichever element of the currently requested set (the first that can be found in the list). For this problem we provide negative results