Primal–Dual Algorithms for Precedence Constrained Covering Problems

Abstract

A covering problem is an integer linear program of type min{cTx∣Ax≥D, 0≤x≤d, x∈ℤ}min{cTx∣Ax≥D, 0≤x≤d, x∈Z} where A∈ℤm×n+A∈Z+m×n, D∈ℤm+D∈Z+m, and c,d∈ℤn+c,d∈Z+n. In this paper, we study covering problems with additional precedence constraints {xi≤xj ∀j⪯i∈}{xi≤xj ∀j⪯i∈P}, where =([n],⪯)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=1m=1 and d≡1d≡1. Our main result is a strongly-polynomial primal–dual approximation algorithm for PCCP with d≡1d≡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 P, that is, by the size of a maximum antichain in 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 P. For the general case with d≢1d≢1, we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions.