A short note on the reducibility of the collapsing knapsack problem

A short note on the reducibility of the collapsing knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20031598
Country: Japan
Volume: 45
Issue: 3
Start Page Number: 293
End Page Number: 298
Publication Date: Sep 2002
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: programming: integer
Abstract:

This paper deals with the collapsing knapsack problem. In the literature, to solve the problem, a method incorporating a reduction from the problem to the 0–1 knapsack problem has been proposed. In this paper we show an alternative reduction which produces coefficients smaller than those by the previous. The improvement makes it possible to solve the resulting 0–1 knapsack problem faster than the previous. On our estimation in a case, the efficiency attains up to 150 times. We also show that the coefficients produced will be the smallest possible.

Reviews

Required fields are marked *. Your email address will not be published.