Precedence-constrained covering problems with multiplicity constraints

We study the approximability of covering problems when the set of items chosen to satisfy the covering constraints must form an ideal of a given partial order. We examine the general case with multiplicity constraints, where item i can be chosen up to $$d_i$$ d i times. For the basic precedence-constrained knapsack problem (PCKP) we answer an open question of McCormick et al. (Algorithmica 783:771–787, 2017) and show the existence of approximation algorithms with strongly-polynomial bounds. PCKP is a special case, with a single covering constraint, of a precedence-constrained covering integer program (PCCP). For a general PCCP where the number of covering constraints is $$m \ge 1,$$ m ≥ 1 , we show that an algorithm of Pritchard and Chakrabarty (Algorithmica 611:75–93, 2011) for covering integer programs can be extended to yield an f-approximation, where f is the maximum number of variables with nonzero coefficients in a covering constraint. This is nearly-optimal under standard complexity-theoretic assumptions and rather surprisingly matches the bound achieved for the problem without precedence constraints.