Paid exchanges are worth the price Abstract   We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan  13 . An instance of the problem consists of a sequence of requests to access items in a linked list. After an item is accessed, that item can be moved to any position forward in the list at no cost (a move called free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (a move called paid exchange). The cost to access an item is equal to its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence.  We show a lower bound of 1211 on the worstcase ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers the question of the asymptotic relative power of the two models which has been open since Reingold and Westbrook  11  showed in 1996 that Sleator and Tarjan erred in  13  when they claimed that the two models are equivalent.

Approximation and Hardness of Token Swapping Given a graph G(V,E) with V1,...,n, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2o(n) algorithm under the ETH. This is matched with a simple 2O(n*log(n)) algorithm based on a breadthfirst search in an auxiliary graph. We show one general 4approximation and show APXhardness. Thus, there is a small constant delta u003e 1 such that every polynomial time approximation algorithm has approximation factor at least  :119,results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.