The Library
Almost tight bounds for reordering buffer management
Tools
Tools
Tools
Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke, Harald (2022) Almost tight bounds for reordering buffer management. SIAM Journal on Computing, 51 (3). pp. 701-722. doi:10.1137/20M1326167 ISSN 0097-5397.
|
PDF
WRAP-almost-tight-bounds-reordering-buffer-management-2022.pdf - Published Version - Requires a PDF viewer. Download (960Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-almost-tight-bounds-reordering-buffer-management-Englert-2022.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (505Kb) |
Official URL: https://doi.org/10.1137/20M1326167
Abstract
We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first nontrivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least $\Omega(\sqrt{\log k/\log\log k})$ and randomized online algorithms have a competitive ratio of at least $\Omega(\log\log k)$, where $k$ denotes the size of the buffer. We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of $O(\sqrt{\log k})$, almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani that achieves a competitive ratio of $O(\log k/\log\log k)$.
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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): | Online algorithms, Buffer storage (Computer science), Computer scheduling | ||||||||||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||||||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||
| ISSN: | 0097-5397 | ||||||||||||
| Official Date: | 24 May 2022 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 51 | ||||||||||||
| Number: | 3 | ||||||||||||
| Page Range: | pp. 701-722 | ||||||||||||
| DOI: | 10.1137/20M1326167 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Reuse Statement (publisher, data, author rights): | Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| Date of first compliant deposit: | 28 February 2022 | ||||||||||||
| Date of first compliant Open Access: | 30 May 2022 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| 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
