Approximation algorithms for covering/packing integer programs

Abstract: Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given , finds a solution of cost times optimal, meeting the covering constraints () and multiplicity constraints (), and satisfying , where is the vector of row sums . Here m denotes the number of rows of . This gives an -approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints . The previous best approximation ratio has been since 1982. CIP contains the set cover problem as a special case, so -approximation is the best possible unless . [Copyright &y& Elsevier]