Primal‐Dual Algorithms for Precedence Constrained Covering Problems

A covering problem is an integer linear program of type $min\{c^{T}x\mid Ax\ge D,0\le x\le d,x\in ‐{Z}\}$ where $A\in {‐{Z}}_{+}^{m\times n}$ , $D\in {{Z}}_{+}^m$ , and $c,d\in {{Z}}_{+}^n$ . In this paper, we study covering problems with additional precedence constraints $\{x_i\le x_j\forall j⪯i\in \mathcal{P}\}$ , where $\mathcal{P}=([n],⪯)$ is some arbitrary, but fixed partial order on the items represented by the column‐indices of A. Such precedence constrained covering problems (PCCPs) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem, that is, where $m=1$ and $d\equiv 1$ . Our main result is a strongly‐polynomial primal–dual approximation algorithm for PCCP with $d\equiv 1$ . Our approach generalizes the well‐known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of $\mathcal{P}$ , that is, by the size of a maximum antichain in $\mathcal{P}$ . Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets $\mathcal{P}$ . For the general case with $d\not\equiv 1$ , we present pseudo‐polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions.