Document Open Access Logo

New Bounds for Randomized List Update in the Paid Exchange Model

Authors Susanne Albers, Maximilian Janke

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.12.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technical University of Munich, Germany
Maximilian Janke
  • Department of Computer Science, Technical University of Munich, Germany

Funding

Work supported by the European Research Council, Grant Agreement No. 691672, project APEG.

Cite As Get BibTex

Susanne Albers and Maximilian Janke. New Bounds for Randomized List Update in the Paid Exchange Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.12

Abstract

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 motivated by the fact that, when executing search operations on a data structure, key comparisons are less expensive than item swaps.
We develop a new randomized online algorithm that achieves an improved competitive ratio against oblivious adversaries. For large d, the competitiveness tends to 2.2442. Technically, the analysis of the algorithm relies on a new approach of partitioning request sequences and charging expected cost. Furthermore, we devise lower bounds on the competitiveness of randomized algorithms against oblivious adversaries. No such lower bounds were known before. Specifically, we prove that no randomized online algorithm can achieve a competitive ratio smaller than 2 in the partial cost model, where an access to the i-th item in the current list incurs a cost of i-1 rather than i. All algorithms proposed in the literature attain their competitiveness in the partial cost model. Furthermore, we show that no randomized online algorithm can achieve a competitive ratio smaller than 1.8654 in the standard full cost model. Again the lower bounds hold for large d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • self-organizing lists
  • online algorithm
  • competitive analysis
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Albers. Improved randomized on-line algorithms for the list update problem. SIAM J. Comput., 27(3):682-693, 1998. Google Scholar
  2. S. Albers and S. Lauer. On list update with locality of reference. J. Comput. Syst. Sci., 82(5):627-653, 2016. Google Scholar
  3. S. Albers, B. von Stengel, and R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Inf. Process. Lett., 56(3):135-139, 1995. Google Scholar
  4. S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms, The State of the Art, Springer LNCS 1442, pages 13-51, 1998. Google Scholar
  5. C. Ambühl, B. Gärtner, and B. von Stengel. Optimal lower bounds for projective list update algorithms. ACM Trans. Algorithms, 9(4):31:1-31:18, 2013. Google Scholar
  6. S. Angelopoulos and P. Schweitzer. Paging and list update under bijective analysis. J. ACM, 60(2):7:1-7:18, 2013. Google Scholar
  7. A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  8. J. Boyar, S. Kamali, K.S. Larsen, and A. López-Ortiz. On the list update problem with advice. Inf. Comput., 253:411-423, 2017. Google Scholar
  9. M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, 1994. Google Scholar
  10. M. Crochemore, R. Grossi, J. Kärkkäinen, and G.M. Landau. Computing the Burrows-Wheeler transform in place and in small space. J. Discrete Algorithms, 32:44-52, 2015. Google Scholar
  11. R. Dorrigiv, M.R. Ehmsen, and A. López-Ortiz. Parameterized analysis of paging and list update algorithms. Algorithmica, 71(2):330-353, 2015. Google Scholar
  12. S. Irani. Two results on the list update problem. Inf. Process. Lett., 38(6):301-306, 1991. Google Scholar
  13. S. Kamali, S. Ladra, A. López-Ortiz, and D. Seco. Context-based algorithms for the list-update problem under alternative cost models. In Proc. 2013 Data Compression Conference (DCC), IEEE, pages 361-370, 2013. Google Scholar
  14. S. Kamali and A. López-Ortiz. A survey of algorithms and models for list update. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of his 66th Birthday, pages 251-266, 2013. Google Scholar
  15. S. Kamali and A. López-Ortiz. Better compression through better list update algorithms. In Proc. 2014 Data Compression Conference (DCC), IEEE, pages 372-381, 2014. Google Scholar
  16. R. Karp and P. Raghavan. Personal communication cited in [N. Reingold et al., 1994]. Google Scholar
  17. A. López-Ortiz, M.P. Renault, and A. Rosén. Paid exchanges are worth the price. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS15), LIPIcs 30, pages 636-648, 2015. Google Scholar
  18. M.S. Manasse, L.A. McGeoch, and D.D. Sleator. Competitive algorithms for on-line problems. In Proc. 20th Annual ACM Symposium on Theory of Computing, pages 322-333, 1988. Google Scholar
  19. G. Manzini. An analysis of the Burrows-Wheeler transform. J. ACM, 48(3):407-430, 2001. Google Scholar
  20. C. Martínez and S. Roura. On the competitiveness of the move-to-front rule. Theor. Comput. Sci., 242(1-2):313-325, 2000. Google Scholar
  21. J. McCabe. On serial files with relocatable records. Operations Research, 12:609-618, 1965. Google Scholar
  22. J.I. Munro. On the competitiveness of linear search. In Proc. 8th Annual European Symposium on Algorithms (ESA00), Springer LNCS 1879, pages 338-345, 2000. Google Scholar
  23. N. Reingold and J. Westbrook. Off-line algorithms for the list update problem. Inf. Process. Lett., 60(2):75-80, 1996. Google Scholar
  24. N. Reingold, J. Westbrook, and D.D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica, 11(1):15-32, 1994. Google Scholar
  25. J. Sirén. Burrows-Wheeler transform for terabases. In Proc. 2016 Data Compression Conference (DCC), IEEE, pages 211-220, 2016. Google Scholar
  26. D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. Google Scholar
  27. B. Teia. A lower bound for randomized list update algorithms. IPL, 47(1):5-9, 1993. Google Scholar
  28. A.C.C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th IEEE Annual Symposium on Foundations of Computer Science, pages 222-227, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact