NP-hardness of the sorting buffer problem on the uniform metric

DOI10.1016/j.dam.2012.02.005zbMath1243.68165OpenAlexW2047334728MaRDI QIDQ427885

Eiji Miyano, Kenichi Kawahara, Yuichi Asahiro

Publication date: 18 June 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.02.005

zbMATH Keywords

metric spaceNP-hardnessuniform metricsorting buffer problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer system organization (68M99)

Related Items

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 note on sorting buffers offline, A review of synchronization problems in parts-to-picker warehouses, NP-hardness of the sorting buffer problem on the uniform metric, 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
• Improved online algorithms for the sorting buffer problem on line metrics
• Almost tight bounds for reordering buffer management
• Automata, Languages and Programming
• LATIN 2004: Theoretical Informatics