A Minimal Reduction Approach for the Collapsing Knapsack Problem

Abstract

Within the research releated to NP-hard problems major emphasis is now placed on the attempt to solve as large problems as possible within a given time. This paper follows this approach in relation to Collapsing Knapsack Problem (CKP). The collapsing knapsack problem is a generalized 0-1 knapsack problem where the capacity of the knapsack is a non-increasing function of the number of items included. We generalize a well known reduction approach to a standard knapsack problem (SKP), and propose a new reduction approach which leads to a significantly smaller capacity and to smaller coefficients of the resulting SKP. With the new reduction approach, the capacity of the resulting SKP is reduced from 3nA to 2(n+2)b(1) with b(1) <= A, where A is the total weight of all the items. The MINKNAP algorithm, proposed by Pisinger (1997) to solve SKP, is directly improved because of the moderate coefficients of the resulting SKP. The pseudo-polynomial solution time to solve CKP is reduced from O(n^3a') to O(n^2b(1)), where a' is the upper bound of the weights.