In this chapter we continue our survey with a focus on two variants of the one-dimensional bin packing problem: the variable-sized bin packing problem and the bin covering problem. In Section 34.2, we survey algorithms for packing into bins of different sizes, a problem first studied by Friesen and Langston  in 1986. In Section 34.3, we survey the bin covering problem, which asks for a partition of a given set of items into a maximum number of subsets such that, in every subset, the total item size is always at least some lower bound. This problem was first studied by Assmann et al.  in 1984. Concluding remarks are given in Section 34.4.
|Original language||English (US)|
|Title of host publication||Handbook of Approximation Algorithms and Metaheuristics|
|ISBN (Print)||1584885505, 9781584885504|
|State||Published - Jan 1 2007|
All Science Journal Classification (ASJC) codes
- Computer Science(all)