2026-07-25T18:31:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4449 2024-03-06T10:35:03Z ddc:004 open_access

Generalized Reordering Buffer Management Azar, Yossi Englert, Matthias Gamzu, Iftah Kidron, Eytan online algorithms paging reordering buffer An instance of the generalized reordering buffer management problem consists of a service station that has k servers, each configured with a color, and a buffer of size b. The station needs to serve an online stream of colored items. Whenever an item arrives, it is stored in the buffer. At any point in time, a currently pending item can be served by switching a server to its color. The objective is to serve all items in a way that minimizes the number of servers color switches. This problem generalizes two well-studied online problems: the paging problem, which is the special case when b=1, and the reordering buffer problem, which is the special case when k=1. In this paper, we develop a randomized online algorithm that obtains a competitive ratio of O(sqrt(b).ln(k)). Note that this result beats the easy deterministic lower bound of k whenever b < k^(2-e). We complement our randomized approach by presenting a deterministic algorithm that attains a competitive ratio of O(min{k^2.ln(b),k.b}). We further demonstrate that if our deterministic algorithm can employ k/(1-d) servers where d is in (0,1), then it achieves a competitive ratio of O(min{ln(b/d^2),b/d}) against an optimal offline adversary that employs k servers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yossi Azar and Matthias Englert and Iftah Gamzu and Eytan Kidron 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.87 urn:nbn:de:0030-drops-44498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.87 eng https://creativecommons.org/licenses/by/3.0/legalcode