License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.636
URN: urn:nbn:de:0030-drops-49476
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4947/
Go to the corresponding LIPIcs Volume Portal

López-Ortiz, Alejandro ; Renault, Marc P. ; Rosén, Adi

Paid Exchanges are Worth the Price

pdf-format:
47.pdf (0.6 MB)

Abstract

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [12]. 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 (accrued from accesses and exchanges) over the request sequence.

We show a lower bound of 12/11 on the worst-case 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 an outstanding question that has been open since 1996 [10].

BibTeX - Entry

@InProceedings{lpezortiz_et_al:LIPIcs:2015:4947,
  author =	{Alejandro L{\'o}pez-Ortiz and Marc P. Renault and Adi Ros{\'e}n},
  title =	{{Paid Exchanges are Worth the Price}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{636--648},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4947},
  URN =		{urn:nbn:de:0030-drops-49476},
  doi =		{10.4230/LIPIcs.STACS.2015.636},
  annote =	{Keywords: list update problem, online computation, online algorithms, competitive analysis, lower bounds}
}

Keywords: list update problem, online computation, online algorithms, competitive analysis, lower bounds
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI