TY - GEN
T1 - A fully polynomial approximation scheme for a knapsack problem with a minimum filling constraint (extended abstract)
AU - Xu, Zhou
AU - Lai, Xiaofan
PY - 2011/9/1
Y1 - 2011/9/1
N2 - 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 ≤ α < 1. For any such constant α, since finding an optimal solution is NP-hard, we develop the first FPTAS for the problem, which has a time complexity polynomial in 1/(1 - α).
AB - 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 ≤ α < 1. For any such constant α, since finding an optimal solution is NP-hard, we develop the first FPTAS for the problem, which has a time complexity polynomial in 1/(1 - α).
KW - approximation algorithm
KW - FPTAS
KW - knapsack problem
KW - minimum filling constraint
UR - http://www.scopus.com/inward/record.url?scp=80052107063&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22300-6_61
DO - 10.1007/978-3-642-22300-6_61
M3 - Conference article published in proceeding or book
SN - 9783642222993
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 704
EP - 715
BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011
Y2 - 15 August 2011 through 17 August 2011
ER -