אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

In this work, we consider the list update problem as defined in the seminal work on competitive analysis by [Sleator, Tarjan 85]. In this problem, a sequence of requests, consisting of items to access in a linked list, is given. After an item is accessed it can be moved to any position forward in the list at no cost (free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (paid exchange). The cost to access an item is its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost occurred from accesses and exchanges. We present novel proofs for the competitive ratio of the classic algorithms for the list update problem. We present a novel linear program for the list update problem, and apply the dual fitting technique, to analyse the competitiveness of the classic algorithms to the list update problem: MTF, BIT, TIMESTAMP and COMB. We also present a new and improved lower bound of 5/4 for offline algorithms, that are allowed to use only free exchanges. This is a significant improvement over the previous known lower bound of 12/11.