ALMOST TIGHT BOUNDS FOR REORDERING BUFFER MANAGEMENT

Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Racke

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

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 Ω (√ 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 that achieves a competitive ratio of O(log k/ log log k).

OriginalspracheEnglisch
Seiten (von - bis)701-722
Seitenumfang22
FachzeitschriftSIAM Journal on Computing
Jahrgang51
Ausgabenummer3
DOIs
PublikationsstatusVeröffentlicht - 2022

Fingerprint

Untersuchen Sie die Forschungsthemen von „ALMOST TIGHT BOUNDS FOR REORDERING BUFFER MANAGEMENT“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren