On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs

DOI10.1007/978-3-662-47672-7_7zbMath1422.68269OpenAlexW788380883MaRDI QIDQ3448775

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

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

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

Related Items (3)

Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities ⋮ Logarithmic price of buffer downscaling on line metrics ⋮ Almost Tight Bounds for Reordering Buffer Management

Cites Work

• A note on sorting buffers offline
• A sequential ordering problem in automotive paint shops
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• New Approximations for Reordering Buffer Management
• Optimal online buffer scheduling for block devices
• Almost tight bounds for reordering buffer management
• Automata, Languages and Programming
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs