A note on sorting buffers offline

DOI10.1016/J.TCS.2011.12.077MaRDI QIDQ417998zbMATH OpenOpenAlexWikidataFDO

Authors Ho-Leung Chan, Nicole Megow, Rob van Stee, René 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 algorithmbuffer sortingNP-hardresource augmentation

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)

Recommendations

• scientific article; zbMATH DE number 1947443
• Improved Online Algorithms for the Sorting Buffer Problem
• Offline Sorting Buffers on Line
• Approximation and Online Algorithms
• Exploiting locality: Approximating sorting buffers

Cites work

• 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
• Exploiting locality: Approximating sorting buffers
• scientific article; zbMATH DE number 5485491 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• NP-hardness of the sorting buffer problem on the uniform metric
• Online and offline algorithms for the sorting buffers problem on the line metric

Cited in

(13)

• Reordering buffer management with advice
• The forgotten sons: warehousing systems for brick-and-mortar retail chains
• Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Weighted reordering buffer improved via variants of knapsack covering inequalities
• NP-hardness of the sorting buffer problem on the uniform metric
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• Offline Sorting Buffers on Line
• Almost Tight Bounds for Reordering Buffer Management
• Approximation and Online Algorithms
• LATIN 2004: Theoretical Informatics
• A review of synchronization problems in parts-to-picker warehouses
• Exploiting locality: Approximating sorting buffers

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

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