A note on sorting buffers offline

DOI10.1016/J.TCS.2011.12.077zbMath1237.68034OpenAlexW2149802161WikidataQ57399755 ScholiaQ57399755MaRDI QIDQ417998

Ho-Leung Chan, Rob van Stee, Nicole Megow, R. A. Sitters

Publication date: 14 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.077

zbMATH Keywords

approximation algorithmNP-hardresource augmentationbuffer sorting

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs ⋮ Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities ⋮ Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment ⋮ A review of synchronization problems in parts-to-picker warehouses ⋮ Reordering buffer management with advice ⋮ The forgotten sons: warehousing systems for brick-and-mortar retail chains ⋮ Almost Tight Bounds for Reordering Buffer Management

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of the sorting buffer problem on the uniform metric
• Exploiting locality: Approximating sorting buffers
• Online and offline algorithms for the sorting buffers problem on the line metric
• A sequential ordering problem in automotive paint shops
• Almost tight bounds for reordering buffer management
• Automata, Languages and Programming
• LATIN 2004: Theoretical Informatics

This page was built for publication: A note on sorting buffers offline