Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/27211
Title: The knapsack problem with a minimum filling constraint
Authors: Xu, Z 
Keywords: approximation scheme
knapsack problem
minimum filling constraint
polynomial time
Issue Date: 2013
Publisher: John Wiley & Sons
Source: Naval research logistics, 2013, v. 60, no. 1, p. 56-63 How to cite?
Journal: Naval research logistics 
Abstract: 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-α).
URI: http://hdl.handle.net/10397/27211
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.21520
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

31
Last Week
2
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.