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 -