In the incremental knapsack problem (IK), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of T periods and the capacity of the knapsack is Bt in period t for t = 1,...,T. We are also given a set S of N items to be placed in the knapsack. Item i has a value of vi and a weight of wi that is independent of the time period. At any time period t, the sum of the weights of the items in the knapsack cannot exceed the knapsack capac- ity Bt. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capac- ity constraints. We first give a constant factor approximation algorithm for IK, under mild restrictions on the growth rate of Bt (the constant factor depends on the growth rate). We then give a PTAS for IIK, the special case of IK with no discounting, when T = O( p log N).
A special case of the generalized assignment problem where the items' weight and value are identical across knapsacks is known as the ; for this problem, Chekuri and Khanna @cite_2 developed a PTAS. Moreover, they also showed that two mild generalization of the MKP--- @math and @math or @math and @math --- are APX hard, thus ruling out a PTAS for these generalizations, assuming @math . Again, neither the PTAS nor their hardness results are directly applicable to the @math .
@cite_2
2000444555
The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of @math items and @math bins (knapsacks) such that each item @math has a profit @math and a size @math , and each bin @math has a capacity @math . The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461-474], and thus far, this was also the best known approximation for MKP @. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP @. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with @math distinct sizes and profits.