Title | ||
---|---|---|
A fully polynomial approximation scheme for a knapsack problem with a minimum filling constraint |
Abstract | ||
---|---|---|
We study a variant of the knapsack problem, where a minimum filling constraint is imposed such that the total weight of selected items cannot be less than a given threshold. We consider the case when the ratio of the threshold to the capacity equals a given constant α with 0 ≤ α |
Year | Venue | Keywords |
---|---|---|
2011 | WADS | selected item,knapsack problem,polynomial approximation scheme,total weight,approximation algorithm |
Field | DocType | Citations |
Approximation algorithm,Discrete mathematics,Combinatorics,Polynomial,Continuous knapsack problem,Knapsack problem,Time complexity,Mathematics | Conference | 1 |
PageRank | References | Authors |
0.36 | 9 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zhou Xu | 1 | 208 | 14.97 |
Xiaofan Lai | 2 | 76 | 4.82 |