TY - JOUR
T1 - Simple but efficient approaches for the collapsing knapsack problem
AU - Pferschy, U.
AU - Pisinger, D.
AU - Woeginger, G.J.
PY - 1997
Y1 - 1997
N2 - The collapsing knapsack problem is a generalization of the ordinary knapsack problem, where the knapsack capacity is a non-increasing function of the number of items included. Whereas previous papers on the topic have applied quite involved techniques, the current paper presents and analyzes two rather simple approaches: One approach that is based on the reduction to a standard knapsack problem, and another approach that is based on a simple dynamic programming recursion. Both algorithms have pseudo-polynomial solution times, guaranteeing reasonable solution times for moderate coefficient sizes. Computational experiments are provided to expose the efficiency of the two approaches compared to previous algorithms.
AB - The collapsing knapsack problem is a generalization of the ordinary knapsack problem, where the knapsack capacity is a non-increasing function of the number of items included. Whereas previous papers on the topic have applied quite involved techniques, the current paper presents and analyzes two rather simple approaches: One approach that is based on the reduction to a standard knapsack problem, and another approach that is based on a simple dynamic programming recursion. Both algorithms have pseudo-polynomial solution times, guaranteeing reasonable solution times for moderate coefficient sizes. Computational experiments are provided to expose the efficiency of the two approaches compared to previous algorithms.
U2 - 10.1016/S0166-218X(96)00134-5
DO - 10.1016/S0166-218X(96)00134-5
M3 - Article
SN - 0166-218X
VL - 77
SP - 271
EP - 280
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -