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 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)

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

• 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?)
• 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
• 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)

• A review of synchronization problems in parts-to-picker warehouses
• Offline Sorting Buffers on Line
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• Approximation and Online Algorithms
• The forgotten sons: warehousing systems for brick-and-mortar retail chains
• Almost Tight Bounds for Reordering Buffer Management
• NP-hardness of the sorting buffer problem on the uniform metric
• 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
• LATIN 2004: Theoretical Informatics
• Reordering buffer management with advice
• Weighted reordering buffer improved via variants of knapsack covering inequalities
• 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)