Almost Tight Bounds for Reordering Buffer Management
From MaRDI portal
Publication:5864670
DOI10.1137/20M1326167OpenAlexW4281387385MaRDI QIDQ5864670
Matthias Englert, Anna Adamaszek, Harald Räcke, Artur Czumaj
Publication date: 8 June 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1326167
Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)
Cites Work
- A note on sorting buffers offline
- NP-hardness of the sorting buffer problem on the uniform metric
- Exploiting locality: Approximating sorting buffers
- Reordering buffer management with advice
- Online and offline algorithms for the sorting buffers problem on the line metric
- A Bicriteria Approximation for the Reordering Buffer Problem
- A sequential ordering problem in automotive paint shops
- On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs
- Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- Reordering Buffers with Logarithmic Diameter Dependency for Trees
- An Improved Competitive Algorithm for Reordering Buffer Management
- Online Stochastic Reordering Buffer Scheduling
- New Approximations for Reordering Buffer Management
- Optimal online buffer scheduling for block devices
- Automata, Languages and Programming
- A Constant Factor Approximation Algorithm for Reordering Buffer Management
- LATIN 2004: Theoretical Informatics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Almost Tight Bounds for Reordering Buffer Management
