Document Open Access Logo

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

Authors Matthias Kohler, Harald Räcke

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.33.pdf
  • Filesize: 420 kB
  • 12 pages

Document Identifiers

Author Details

Matthias Kohler
Harald Räcke

Cite As Get BibTex

Matthias Kohler and Harald Räcke. Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.33

Abstract

In the reordering buffer management problem a sequence of requests arrive online in a finite metric space, and have to be processed by a single server. This server is equipped with a request buffer of size k and can decide at each point in time, which request from its buffer to serve next. Servicing of a request is simply done by moving the server to the location of the request. The goal is to process all requests while minimizing the total distance that the server is traveling inside the metric space.

In this paper we present a deterministic algorithm for the reordering buffer management problem that achieves a competitive ratio of O(log Delta + min {log n,log k}) in a finite metric space of n points and aspect ratio Delta. This is the first algorithm that works for general metric spaces and has just a logarithmic dependency on the relevant parameters. The guarantee is memory-robust, i.e., the competitive ratio decreases only slightly when the buffer-size of the optimum is increased to h=(1+\epsilon)k. For memory robust guarantees our bounds are close to optimal.

Subject Classification

Keywords
  • Online algorithms
  • reordering buffer
  • metric spaces
  • scheduling

Metrics

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

References

  1. Amjad Aboud. Correlation clustering with penalties and approximating the reordering buffer management problem. Master’s thesis, Computer Science Department, The Technion - Israel Institute of Technology, 2008. Google Scholar
  2. Anna Adamaszek, Artur Czumaj, Matthias Englert, and Harald Räcke. Almost tight bounds for reordering buffer management. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 607-616, 2011. Google Scholar
  3. Yuichi Asahiro, Kenichi Kawahara, and Eiji Miyano. NP-hardness of the sorting buffer problem on the uniform metric. Discrete Applied Mathematics, 160(10-11):1453-1464, 2012. URL: http://dx.doi.org/10.1016/j.dam.2012.02.005.
  4. Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, and Yuval Rabani. On the randomized competitive ratio of reordering buffer management with non-uniform costs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 78-90, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  5. Noa Avigdor-Elgrabli and Yuval Rabani. A constant factor approximation algorithm for reordering buffer management. In Proceedings ofproc 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 973-984, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.70.
  6. Noa Avigdor-Elgrabli and Yuval Rabani. An optimal randomized online algorithm algorithm for reordering buffer management. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1-10, 2013. Google Scholar
  7. Noa Avigdor-Elgrabli and Yuval Rabani. An improved competitive algorithm for reordering buffer management. ACM Trans. Algorithms, 11(4):1-15, June 2015. URL: http://dx.doi.org/10.1145/2663347.
  8. Siddharth Barman, Shuchi Chawla, and Seeun Umboh. A bicriteria approximation for the reordering buffer problem. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 157-168, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_15.
  9. Marcin Bienkowski, Martin Böhm, Lukasz Jez, Pawel Laskos-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, and Pavel Veselý. Logarithmic price of buffer downscaling on line metrics. CoRR, abs/1610.04915, 2016. Google Scholar
  10. Dan Blandford and Guy Blelloch. Index compression through document reordering. In Proceedings of the Data Compression Conference, DCC'02, pages 342-351, Washington, DC, USA, 2002. IEEE Computer Society. Google Scholar
  11. Ho-Leung Chan, Nicole Megow, René Sitters, and Rob van Stee. A note on sorting buffers offline. Theoretical Computer Science, 423:11-18, 2012. Google Scholar
  12. Matthias Englert and Harald Räcke. Reordering buffers with logarithmic diameter dependency for trees. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SIDA), pages 1224-1234, 2017. Google Scholar
  13. Matthias Englert and Matthias Westermann. Reordering buffer management for non-uniform cost models. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 627-638, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  14. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004. Google Scholar
  15. Iftah Gamzu and Danny Segev. Improved online algorithms for the sorting buffer problem on line metrics. ACM Trans. Algorithms, 6(1):15:1-15:14, December 2009. Google Scholar
  16. Naveen Garg. Saving an ε: A 2-approximation for the k-MST problem in graphs. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 396-402, 2005. Google Scholar
  17. Kai Gutenschwager, Sven Spiekermann, and Stefan Voß. A sequential ordering problem in automotive paint shops. International Journal of Production Research, 42(9):1865-1878, 2004. URL: http://dx.doi.org/10.1080/00207540310001646821.
  18. Sungjin Im and Benjamin Moseley. New approximations for reordering buffer management. In Proceedings of 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1093-1111, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.81.
  19. Sungjin Im and Benjamin Moseley. Weighted reordering buffer improved via variants of knapsack covering inequalities. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 737-748, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_60.
  20. Rohit Khandekar and Vinayaka Pandit. Online sorting buffers on line. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 584-595, 2006. Google Scholar
  21. Jens Krokowski, Harald Räcke, Christian Sohler, and Matthias Westermann. Reducing state changes with a pipeline buffer. In Proceedings of the 9th International Fall Workshop Vision, Modeling, and Visualization, 2004. Google Scholar
  22. Harald Räcke, Christian Sohler, and Matthias Westermann. Online scheduling for sorting buffers. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA), pages 820-832, 2002. 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