Approximation Schemes for Knapsack Problems with Shelf Divisions

Given a knapsack of size K, non-negative values d and ∆, and a set S of items, each item e ∈ S with size se and value ve, we define a shelf as a subset of items packed inside a bin with total items size at most ∆. Two subsequent shelves must be separated by a shelf divisor of size d. The size of a shelf is the total size of its items plus the size of the shelf divisor. The Shelf-Knapsack Problem (SK) is to find a subset S ′ ⊆ S partitioned into shelves with total shelves size at most K and maximum value. The Class Constrained Shelf Knapsack (CCSK) is a generalization of the problem SK, where each item in S has a class and each shelf in the solution must have only items of the same class. We present approximation schemes for the SK and the CCSK problems. To our knowledge, these are the first approximation results where shelves of non-null size are used in knapsack problems