Improved Algorithms for Variants of Bin Packing and Knapsack

Abstract

We study variants of two classical optimization problems: Bin Packing and Knapsack. Both bin packing and knapsack fall under the regime of "Packing and Covering Problems". In bin packing, we are given a set of input items, each with an associated size, and the objective is to pack these into the minimum number of unit capacity bins. On the other hand, in the knapsack problem, each item has an additional profit associated with it. The objective is to find a maximum profitable subset that can be packed into a unit capacity knapsack. Both bin packing and knapsack find numerous applications; however, both turn out to be NP-Hard. Hence, it is natural to seek approximation algorithms for these problems. Lawler settled the knapsack problem by giving an FPTAS, whereas the progressive works of de la Vega and Lueker, Karmarkar and Karp, and Rothvoss have given improved approximation schemes for the bin packing problem. However, many variants of these problems (e.g., multidimensional, geometric, stochastic) also find wide applicability, but haven't been settled. We make progress on this front by providing new and improved algorithms for several such variants.

First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one, and their sizes are revealed upon their arrival, and they must be packed immediately and irrevocably in bins of unit size. We provide a simple meta-algorithm that takes an offline \alpha-asymptotic approximation algorithm and provides a polynomial-time (\alpha+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, where \epsilon>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time (1+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, thus settling the problem.

Then we study a well-known geometric generalization of the knapsack problem, the 3-D Knapsack problem. In this problem, the items are cuboids in three dimensions, and the knapsack is a unit cube. The objective is to pack a maximum profitable subset of the input set in a non-overlapping, axis-parallel manner inside the knapsack. Depending on whether rotations around axes (by ninety degrees) are allowed or not, we obtain two variants. [DHJTT'07] gave a (7+\epsilon) (resp. (5+\epsilon)) approximation algorithm for the 3D Knapsack problem without rotations (resp. with rotations). Despite the importance of the problem, there has been no improvement in the ratios for fifteen years. First, we give alternate algorithms that achieve the same approximation ratios (7+\epsilon, 5+\epsilon). These algorithms and their analyses are far simpler. Then, for the case when rotations are allowed, we give an improved (31/7+\epsilon) approximation algorithm in the general setting, and a (3+\epsilon) approximation algorithm in the important special case where each item has a profit equal to its volume.

We also introduce and study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and d nonnegative weights (dD vector), and a square knapsack. The goal is to find a non-overlapping, axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the d dimensions does not exceed one. Two variants are defined: rotations allowed by 90 degrees and rotations not allowed. We give (2+\epsilon)-approximation algorithms for both variants.

Finally, we consider the problem of packing d-D hypercubes into a knapsack defined by the region [0,1]^d. Each hypercube has an associated profit, and the goal is to find a maximum profitable non-overlapping, axis-parallel packing. We consider two special cases of this problem: (i) cardinality case, where each item has unit profit, (ii) bounded profit-volume ratio case, where the profit-to-volume ratio of each item lies in the range [1,r] for some fixed constant r. We give near-optimal algorithms for both cases.