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 -