Reordering buffer management with a logarithmic guarantee in general metric spaces

Matthias Kohler, Harald Räcke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

2 Zitate (Scopus)

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.

OriginalspracheEnglisch
Titel44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Redakteure/-innenAnca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959770415
DOIs
PublikationsstatusVeröffentlicht - 1 Juli 2017
Veranstaltung44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Polen
Dauer: 10 Juli 201714 Juli 2017

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band80
ISSN (Print)1868-8969

Konferenz

Konferenz44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Land/GebietPolen
OrtWarsaw
Zeitraum10/07/1714/07/17

Fingerprint

Untersuchen Sie die Forschungsthemen von „Reordering buffer management with a logarithmic guarantee in general metric spaces“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren