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

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
• 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
• Almost tight bounds for reordering buffer management
• Automata, Languages and Programming
• LATIN 2004: Theoretical Informatics

This page was built for publication: NP-hardness of the sorting buffer problem on the uniform metric