Abstract
In the offline list update problem, we maintain an unsorted linear list used as a dictionary. Accessing the item at position i in the list costs i units. In order to reduce access cost, we are allowed to update the list at any time by trans-posing consecutive items at a cost of one unit. Given a sequence σ of requests one has to serve in turn, we are interested in the minimal cost needed to serve all requests. Little is known about this problem. The best algorithm so far needs exponential time in the number of items in the list. We show that there is no poly-nomial algorithm unless P = NP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Albers (1998), Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27, no. 3, 682–693 (electronic). Preliminary version in Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms (1995), 412–419.
S. Albers, B. vonStengel, and R. Werchner (1995), A combined BIT and TIMESTAMP algorithm for the list update problem. Inform. Process. Lett. 56, 135–139. S. Albers (1995), Improved randomized on-line algorithms for the list update problem, Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 412–419.
S. Albers (1998), A competitive analysis of the list update problem with lookahead. Theoret. Comput. Sci. 197, no. 1–2, 95–109.
S. Albers and J. Westbrook (1998), Self Organizing Data Structures. In A. Fiat, G. J. Woeginger, “Online Algorithms: The State of the Art”, Lecture Notes in Comput. Sci., 1442, Springer, Berlin, 13–51.
C. Ambühl, B. Gärtner, and B. von Stengel (2000), A new lower bound for the list update problem in the partial cost model. To appear in Theoret. Comput. Sci.
C. Ambühl, B. Gärtner, and B. von Stengel (2000), Optimal Projective Bounds for the List Update Problem. To appear in Proc. 27th ICALP.
J. L. Bentley, and C. C. McGeoch (1985), Amortized analyses of self-organizing sequential search heuristics. Comm. ACM 28, 404–411.
A. Borodin and R. El-Yaniv (1998), Online Computation and Competitive Analysis. Cambridge Univ. Press, Cambridge.
F. d’Amore, A. Marchetti-Spaccamela, and U. Nanni (1993), The weighted list update problem and the lazy adversary. Theoret. Comput. Sci. 108, no. 2, 371–384
S. Irani (1991), Two results on the list update problem. Inform. Process. Lett. 38, 301–306.
S. Irani (1996), Corrected version of the SPLIT
M. R. Garey, D. S. Johnson (1979), Computers and intractability. W. H. Freeman and Co, San Francisco.
M. Manasse, L. A. McGeoch, and D. Sleator (1988), Competitive algorithms for online problems. Proc. 20nd STOC (1988), 322–333.
N. Reingold, and J. Westbrook (1996), Off-line algorithms for the list update problem. Inform. Process. Lett. 60, no. 2, 75–80. Technical Report YALEU/DCS/TR-805, Yale University.
N. Reingold, J. Westbrook, and D. D. Sleator (1994), Randomized competitive algorithms for the list update problem. Algorithmica 11, 15–32.
D. D. Sleator, and R. E. Tarjan (1985), Amortized efficiency of list update and paging rules. Comm. ACM 28, 202–208.
B. Teia (1993), A lower bound for randomized list update algorithms, Inform. Process. Lett. 47, 5–9.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambühl, C. (2000). Offline List Update is NP-hard. In: Paterson, M.S. (eds) Algorithms - ESA 2000. ESA 2000. Lecture Notes in Computer Science, vol 1879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45253-2_5
Download citation
DOI: https://doi.org/10.1007/3-540-45253-2_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41004-1
Online ISBN: 978-3-540-45253-9
eBook Packages: Springer Book Archive