Almost tight bounds for reordering buffer management

Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

26 Scopus citations

Abstract

We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(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(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).

Original languageEnglish
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages607-616
Number of pages10
ISBN (Print)9781450306911
DOIs
StatePublished - 2011
Externally publishedYes
Event43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, United States
Duration: 6 Jun 20118 Jun 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference43rd ACM Symposium on Theory of Computing, STOC 2011
Country/TerritoryUnited States
CitySan Jose
Period6/06/118/06/11

Keywords

  • online algorithms
  • reordering buffer
  • sorting buffer

Fingerprint

Dive into the research topics of 'Almost tight bounds for reordering buffer management'. Together they form a unique fingerprint.

Cite this