@inproceedings{96b31e010add45ee9294f73bc55b829b,
title = "Reordering buffer management with a logarithmic guarantee in general metric spaces",
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 travelling 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Δ+min{log n, log k}) in a finite metric space of n points and aspect ratio Δ. This is the first algorithm that works for general metric spaces and has just a logarithmic dependency on the relevant parameters. The guarantee is memoryrobust, i.e., the competitive ratio decreases only slightly when the buffer-size of the optimum is increased to h = (1 + ∈)k. For memory robust guarantees our bounds are close to optimal.",
keywords = "Metric spaces, Online algorithms, Reordering buffer, Scheduling",
author = "Matthias Kohler and Harald R{\"a}cke",
note = "Publisher Copyright: {\textcopyright} Matthias Kohler and Harald R{\"a}cke.; 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 ; Conference date: 10-07-2017 Through 14-07-2017",
year = "2017",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2017.33",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Anca Muscholl and Piotr Indyk and Fabian Kuhn and Ioannis Chatzigiannakis",
booktitle = "44th International Colloquium on Automata, Languages, and Programming, ICALP 2017",
}