Premium
The knapsack problem with a minimum filling constraint
Author(s) -
Xu Zhou
Publication year - 2013
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21520
Subject(s) - knapsack problem , continuous knapsack problem , polynomial time approximation scheme , mathematical optimization , constraint (computer aided design) , cutting stock problem , mathematics , profit (economics) , procurement , change making problem , packing problems , computer science , optimization problem , economics , microeconomics , geometry , management
We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e‐commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP‐hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 ‐ ε ) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ ε , and 1/(1‐α). © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013