A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint

摘要

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 a, 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 -a).