Almost tight bounds for reordering buffer management
From MaRDI portal
Publication:5419131
DOI10.1145/1993636.1993717zbMath1288.68031OpenAlexW2059878569WikidataQ58203684 ScholiaQ58203684MaRDI QIDQ5419131
Harald Räcke, Anna Adamaszek, Matthias Englert, Artur Czumaj
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1993636.1993717
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs ⋮ Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities ⋮ Logarithmic price of buffer downscaling on line metrics ⋮ A note on sorting buffers offline ⋮ NP-hardness of the sorting buffer problem on the uniform metric ⋮ Reordering buffer management with advice ⋮ Stochastic dominance and the bijective ratio of online algorithms
