Almost tight bounds for reordering buffer management

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

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

26 Zitate (Scopus)

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).

OriginalspracheEnglisch
TitelSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
Herausgeber (Verlag)Association for Computing Machinery
Seiten607-616
Seitenumfang10
ISBN (Print)9781450306911
DOIs
PublikationsstatusVeröffentlicht - 2011
Extern publiziertJa
Veranstaltung43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, USA/Vereinigte Staaten
Dauer: 6 Juni 20118 Juni 2011

Publikationsreihe

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

Konferenz

Konferenz43rd ACM Symposium on Theory of Computing, STOC 2011
Land/GebietUSA/Vereinigte Staaten
OrtSan Jose
Zeitraum6/06/118/06/11

Fingerprint

Untersuchen Sie die Forschungsthemen von „Almost tight bounds for reordering buffer management“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren