Given matrices A and B and vectors a, b, c and d, all with
non-negative entries, we consider the problem of minimizing c$\cdot$x
subject to x$\in Z^n_+$, Ax ≥ a, Bx ≤ b, and x ≤ d.
We give a bicriteria-approximation algorithm that, given
ε$\in$(0, 1], finds a solution of cost O(log(m)/ε2
times optimal, meeting the covering constraints Ax≥a and
multiplicity constraints (x≤d), and satisfying Bx≤(1 + ε)b + β,
where β is the vector of row sums, β_i=$\sum_j$ Bij
Here m is the number of rows of A.
This gives an O(log m)-approximation algorithm for CIP
--- minimum-cost covering integer programs with multiplicity constraints,
i.e., the special case when there are no packing constraints Bx ≤ b.
The previous best approximation ratio has been
since 1982. CIP contains the set cover problem as a special case,
so O(log m)-approximation is the best possible unless P=NP.