On the randomized competitive ratio of reordering buffer management with non-uniform costs

DOI10.1007/978-3-662-47672-7_7MaRDI QIDQ3448775zbMATH OpenOpenAlexFDO

Authors Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, Yuval Rabani

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47672-7_7

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Automata, Languages and Programming
• An improved competitive algorithm for reordering buffer management
• An improved competitive algorithm for reordering buffer management
• New Approximations for Reordering Buffer Management
• Generalized Reordering Buffer Management

Cites work

• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• A note on sorting buffers offline
• A sequential ordering problem in automotive paint shops
• Almost tight bounds for reordering buffer management
• An improved competitive algorithm for reordering buffer management
• Automata, Languages and Programming
• scientific article; zbMATH DE number 5899288 (Why is no real title available?)
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• Improved online algorithms for the sorting buffer problem on line metrics
• New Approximations for Reordering Buffer Management
• Optimal online buffer scheduling for block devices
• The Design of Competitive Online Algorithms via a Primal—Dual Approach

Cited in

(9)

• Logarithmic price of buffer downscaling on line metrics
• Weighted reordering buffer improved via variants of knapsack covering inequalities
• An improved competitive algorithm for reordering buffer management
• New Approximations for Reordering Buffer Management
• An improved competitive algorithm for reordering buffer management
• 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: On the randomized competitive ratio of reordering buffer management with non-uniform costs

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