1 Search Results for "Kohler, Matthias"

Document
DOI: 10.4230/LIPIcs.ICALP.2017.33
Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

Authors: Matthias Kohler and Harald Räcke

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{kohler_et_al:LIPIcs.ICALP.2017.33,
  author =	{Kohler, Matthias and R\"{a}cke, Harald},
  title =	{{Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.33},
  URN =		{urn:nbn:de:0030-drops-73882},
  doi =		{10.4230/LIPIcs.ICALP.2017.33},
  annote =	{Keywords: Online algorithms, reordering buffer, metric spaces, scheduling}
}
  • Refine by Author
  • 1 Kohler, Matthias
  • 1 Räcke, Harald

  • Refine by Classification

  • Refine by Keyword
  • 1 Online algorithms
  • 1 metric spaces
  • 1 reordering buffer
  • 1 scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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 Imprint Privacy Contact