An improved competitive algorithm for reordering buffer management

MaRDI QIDQ5417601zbMATH OpenFDO

Authors Noa Avigdor-Elgrabli, Yuval Rabani

Publication date 22 May 2014

zbMATH Keywords

buffer managementlinear programmingnon-uniform costsonline algorithmspolynomial time approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Linear programming (90C05)

Recommendations

• An improved competitive algorithm for reordering buffer management
• Almost tight bounds for reordering buffer management
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Automata, Languages and Programming
• New Approximations for Reordering Buffer Management

Cited in

(16)

• Logarithmic price of buffer downscaling on line metrics
• Reordering buffer management with advice
• Generalized Reordering Buffer Management
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Weighted reordering buffer improved via variants of knapsack covering inequalities
• A note on sorting buffers offline
• NP-hardness of the sorting buffer problem on the uniform metric
• An improved competitive algorithm for reordering buffer management
• Tight bounds for online coloring of basic graph classes
• Evaluation of Online Strategies for Reordering Buffers
• New Approximations for Reordering Buffer Management
• Evaluation of online strategies for reordering buffers
• Almost tight bounds for reordering buffer management
• Automata, Languages and Programming
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• Almost Tight Bounds for Reordering Buffer Management

This page was built for publication: An improved competitive algorithm for reordering buffer management

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