Algorithms for the List Update Problem

List Update problem has been studied extensively in the area of on-line algorithms. In this problem we need to maintain a linear list of items and serve a sequence of requests like access, insert and delete on it. After each request the items if the list may be rearranged in order to make next request ecient. Apart from the requests, the reordering of the list also incurs cost. The goal of the algorithm in order to minimize the total cost of serving request and list reordering. In this thesis we have proposed some algorithms for o-line as well as on-line solution to the list update problem. The off-lin