Notes on inverse bin-packing problems

作者：Chung Yerim; Park Myoung Ju^*

来源：Information Processing Letters, 2015, 115(1): 60-68.

DOI：10.1016/j.ipl.2014.09.005

• Inverse optimization
• Combinatorial problems
• Bin-packing problem
• NP-hardness
• Approximation algorithms

In bin-packing problems, given items need to be packed using a minimum number of bins. Inverse bin-packing number problems, IBPN for short, assume a given set of items and number of bins. The objective is to achieve the minimum perturbation to the item-size vector so that all the items can be packed into the prescribed number of bins. In this paper, complexity status and approximation behavior for IBPN were investigated. Under the L-p-norm, for all p is an element of {1,2...,infinity} IBPN turns out to be NP-hard in the strong sense. IBPN under the L-1-norm admits a polynomial time differential approximation scheme, and a fully polynomial time approximation scheme if a constant number of machines is provided as input. We also consider another IBPN variant where a specified feasible solution is given instead of a target bin number. The objective is to make the given solution optimal with minimum modification. We provide the hardness result for this problem.

• 出版日期2015-1