Precedence-constrained knapsack is a generalization of the classical Minimum Knapsack problem in which the items chosen for inclusion in the knapsack must form a prefix (ideal) of a given partial order. We study primal-dual algorithms from the literature and among other results we settle the question of the existence of an approximation algorithm with strongly polynomial bounds for the case where item i can be chosen at most d_i times (as opposed to at most once).
Capacitated covering integer programs generalize Minimum Knapsack in the sense that the items chosen must satisfy simultaneously m covering constraints. For this problem we improve the efficiency of a known approximatio algorithms.
All our positive and negative results rely on linear programming relaxations for the problems.