Reordering buffers with logarithmic diameter dependency for trees

Matthias Englert, Harald Racke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

8 Zitate (Scopus)

Abstract

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. The goal is to process all items while minimizing the total distance the server moves. Englert, Racke, Westermann (STOC'07) gave a deterministic O(D log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(logD+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h(logD+log h)=k)- competitive. For h = (1 + ϵ) , with constant > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n . log2 k) result for n-point metric spaces from STOC'07 to O(log n log k).

OriginalspracheEnglisch
Titel28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Redakteure/-innenPhilip N. Klein
Herausgeber (Verlag)Association for Computing Machinery
Seiten1224-1234
Seitenumfang11
ISBN (elektronisch)9781611974782
DOIs
PublikationsstatusVeröffentlicht - 2017
Veranstaltung28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spanien
Dauer: 16 Jan. 201719 Jan. 2017

Publikationsreihe

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Band0

Konferenz

Konferenz28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Land/GebietSpanien
OrtBarcelona
Zeitraum16/01/1719/01/17

Fingerprint

Untersuchen Sie die Forschungsthemen von „Reordering buffers with logarithmic diameter dependency for trees“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren