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 di\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_i$$\end{document} 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≥1,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \ge 1,$$\end{document} 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.