The Library
Generalized reordering buffer management
Tools
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
|
PDF
WRAP_Englert_Generalized_7.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (750Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.87
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: |
|
||||
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) | ||||
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: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year