TY - GEN

T1 - Reordering buffers with logarithmic diameter dependency for trees

AU - Englert, Matthias

AU - Racke, Harald

N1 - Publisher Copyright:
Copyright © by SIAM.

PY - 2017

Y1 - 2017

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85016210011&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.79

DO - 10.1137/1.9781611974782.79

M3 - Conference contribution

AN - SCOPUS:85016210011

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1224

EP - 1234

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -