TY - GEN

T1 - Polylogarithmic guarantees for generalized reordering buffer management

AU - Englert, Matthias

AU - Racke, Harald

AU - Stotz, Richard

N1 - Publisher Copyright:
© 2019 IEEE.

PY - 2019/11

Y1 - 2019/11

N2 - In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrives online, and has to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server. Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers. This problem was introduced in [Chan, Megow, Sitters, van Stee TCS 12] and has been subsequently studied in an online setting by [Azar, Englert, Gamzu, Kidron STACS 14]. The problem is a natural generalization of two very well-studied problems: The k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. In this paper we consider the GRBM problem on a uniform metric in the online version. We show how to obtain a competitive ratio of O(log k(log k+loglog b)) for this problem. Our result is a drastic improvement in the dependency on b compared to the previous best bound of O(√b log k), and is asymptotically optimal for constant k, because Ω(log k + loglog b) is a lower bound for GRBM on uniform metrics.

AB - In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrives online, and has to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server. Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers. This problem was introduced in [Chan, Megow, Sitters, van Stee TCS 12] and has been subsequently studied in an online setting by [Azar, Englert, Gamzu, Kidron STACS 14]. The problem is a natural generalization of two very well-studied problems: The k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. In this paper we consider the GRBM problem on a uniform metric in the online version. We show how to obtain a competitive ratio of O(log k(log k+loglog b)) for this problem. Our result is a drastic improvement in the dependency on b compared to the previous best bound of O(√b log k), and is asymptotically optimal for constant k, because Ω(log k + loglog b) is a lower bound for GRBM on uniform metrics.

KW - Online computing

KW - Randomized algorithms

KW - Reordering buffer management

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

U2 - 10.1109/FOCS.2019.00012

DO - 10.1109/FOCS.2019.00012

M3 - Conference contribution

AN - SCOPUS:85078418374

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 38

EP - 59

BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019

PB - IEEE Computer Society

T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019

Y2 - 9 November 2019 through 12 November 2019

ER -