The Library
Polylogarithmic guarantees for generalized reordering buffer management
Tools
Englert, Matthias, Räcke, Harald and Stotz, Richard (2020) Polylogarithmic guarantees for generalized reordering buffer management. In: FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science , , Baltimore, Maryland, 9-12 Nov 2019. Published in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS.2019.00012 ISSN 2575-8454.
|
PDF
WRAP-polylogarithmic-gurarantees-buffer-management-Englert-2019.pdf - Accepted Version - Requires a PDF viewer. Download (723Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS.2019.00012
Abstract
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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics 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): | Programming languages (Electronic computers) , Computer programming , Machine theory , Logarithmic functions | ||||||
Journal or Publication Title: | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) | ||||||
Publisher: | IEEE | ||||||
ISSN: | 2575-8454 | ||||||
Official Date: | 6 January 2020 | ||||||
Dates: |
|
||||||
DOI: | 10.1109/FOCS.2019.00012 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 30 September 2019 | ||||||
Date of first compliant Open Access: | 30 September 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science , | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Baltimore, Maryland | ||||||
Date(s) of Event: | 9-12 Nov 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year