Almost Tight Bounds for Reordering Buffer Management

DOI10.1137/20M1326167MaRDI QIDQ5864670zbMATH OpenOpenAlexFDO

Authors Anna Adamaszek, Matthias Englert, 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

zbMATH Keywords

online algorithmsreordering buffersscheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Almost tight bounds for reordering buffer management
• New Approximations for Reordering Buffer Management
• scientific article; zbMATH DE number 7204485
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• An improved competitive algorithm for reordering buffer management
• An improved competitive algorithm for reordering buffer management
• Generalized Reordering Buffer Management
• A bicriteria approximation for the reordering buffer problem
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Evaluation of Online Strategies for Reordering Buffers

Cites work

• A bicriteria approximation for the reordering buffer problem
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• A note on sorting buffers offline
• A sequential ordering problem in automotive paint shops
• An improved competitive algorithm for reordering buffer management
• Automata, Languages and Programming
• Exploiting locality: Approximating sorting buffers
• scientific article; zbMATH DE number 5899288 (Why is no real title available?)
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• scientific article; zbMATH DE number 7204485 (Why is no real title available?)
• Improved online algorithms for the sorting buffer problem on line metrics
• LATIN 2004: Theoretical Informatics
• New Approximations for Reordering Buffer Management
• NP-hardness of the sorting buffer problem on the uniform metric
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Online and offline algorithms for the sorting buffers problem on the line metric
• Online stochastic reordering buffer scheduling
• Optimal online buffer scheduling for block devices
• Reordering buffer management with advice
• Reordering buffers with logarithmic diameter dependency for trees
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Weighted reordering buffer improved via variants of knapsack covering inequalities

Cited in

(9)

• Generalized Reordering Buffer Management
• scientific article; zbMATH DE number 5899288 (Why is no real title available?)
• Nearly optimal FIFO buffer management for DiffServ
• New Approximations for Reordering Buffer Management
• Buffered Resource Constraint: Algorithms and Complexity
• Almost tight bounds for reordering buffer management
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• Buffer minimization with conflicts on a line
• Complexity of fixed order routing

This page was built for publication: Almost Tight Bounds for Reordering Buffer Management

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864670)