Two Dimensional Knapsack with Unloading Constraints

n this paper we present approximation algorithms for the two dimensional knapsack problem with unloading constraints. In this problem, we have a bin B of width and height 1, and a list L with n items of C different classes, each item ai with height h(ai), width w(ai), profit p(ai) and class c(ai). We have to pack a subset of the items of L into B, without rotations or overlaps, maximizing the total profit of packed items. In our problem the right side of the bin corresponds to the entry and leaving place of items. The class value of each item is an integer that indicates the order in which items must be unloaded from the bin. The generated packing must satisfy the unloading constraints: while removing one item, other items of higher classes can not block the way out of the item. We present a (4+ϵ)-approximation algorithm to this problem, a (3+ϵ)-approximation algorithm for the special case where profits are proportional to the items area, and a (3+ϵ)-approximation for the case in which the items are squares.