Some Complexity Results for the Minimum Blocking Items Problem

Authors: T. Bacci, S. Mattia, and P. Ventura

Book: Optimization and Decision Science: Methodologies and Applications

URL: http://doi.org/10.1007/978-3-319-67308-0_48

Abstract: In this paper, we study the Minimum Blocking Items Problem (MBIP) as a generalization of the Bounded Coloring Problem for Permutation Graphs and we motivate our interest by discussing some practical applications of MBIP to the context of minimizing reshuffle operations in a container yard. Then we present some results on the computational complexity of MBIP.

Keywords: Bounded coloring problem, Block relocation problem, Complexity.