Azar, Yossi, Englert, Matthias, Gamzu, Iftah and Kidron, Eytan (2014) Generalized reordering buffer management. In: STACS ’14: 31st International Symposium on Theoretical Aspects of Computer Science, Lyon, France, 5-8 Mar 2014. Published in: 31st International Symposium on Theoretical Aspects of Computer Science (STACS ’14) pp. 87-98. doi:10.4230/LIPIcs.STACS.2014.87
Preview |
PDF
WRAP_Englert_Generalized_7.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution . Download (768kB) | Preview |
Abstract
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.
Item Type: | Conference Item (Paper) |
---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
Library of Congress Subject Headings (LCSH): | Buffer storage (Computer science) -- Mathematical models |
Journal or Publication Title: | 31st International Symposium on Theoretical Aspects of Computer Science (STACS ’14) |
Publisher: | Leibniz International Proceedings in Informatics |
Official Date: | 19 February 2014 |
Dates: | Date Event 19 February 2014 Published |
Page Range: | pp. 87-98 |
DOI: | 10.4230/LIPIcs.STACS.2014.87 |
Status: | Peer Reviewed |
Publication Status: | Published |
Access rights to Published version: | Open Access (Creative Commons open licence) |
Date of first compliant deposit: | 28 December 2015 |
Date of first compliant Open Access: | 28 December 2015 |
Funder: | Israel Science Foundation (ISF), Israeli Centers of Research Excellence (I-CORE), Engineering and Physical Sciences Research Council (EPSRC) |
Grant number: | 1404/10 (ISF), 4/11 (I-CORE), EP/D063191/1 (EPSRC), EP/F043333/1 (EPSRC) |
Embodied As: | 1 |
Conference Paper Type: | Paper |
Title of Event: | STACS ’14: 31st International Symposium on Theoretical Aspects of Computer Science |
Type of Event: | Conference |
Location of Event: | Lyon, France |
Date(s) of Event: | 5-8 Mar 2014 |
Related URLs: | |
URI: | https://wrap.warwick.ac.uk/65030/ |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |