About fully polynomial approximability of the generalized knapsack problem

The generalized knapsack problem or gknap is the combinatorial optimization problem of optimizing a nonnegative linear function over the integral hull of the intersection of a polynomially separable 0–1 polytope and a knapsack constraint. The knapsack, the restricted shortest path, and the constrained spanning tree problem are a partial list of gknap. More interestingly, all the problems that are known to have a fully polynomial approximation scheme, or FPTAS are gknap. We establish some necessary and sufficient conditions for a gknap to admit an FPTAS. To do so, we recapture the standard scaling and approximate binary search techniques in the framework of gknap. This also enables us to find a weaker sufficient condition than the strong NP-hardness that a gknap does not have an FPTAS. Finally, we apply the conditions to explore the fully polynomial approximability of the constrained spanning problem whose fully polynomial approximability is still open.