New Bounds for Randomized List Update in the Paid Exchange Model

Susanne Albers & Maximilian Janke
We study the fundamental list update problem in the paid exchange model P^d. This cost model was introduced by Manasse, McGeoch and Sleator [M.S. Manasse et al., 1988] and Reingold, Westbrook and Sleator [N. Reingold et al., 1994]. Here the given list of items may only be rearranged using paid exchanges; each swap of two adjacent items in the list incurs a cost of d. Free exchanges of items are not allowed. The model is...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.