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 min {c.x: x in Z^n_+, Ax > a, Bx < b, x < d}. We give a bicriteria-approximation algorithm that, given epsilon in (0, 1], finds a solution of cost O(ln(m)/epsilon^2) times optimal, meeting the covering constraints (Ax > a) and multiplicity constraints (x < d), and satisfying Bx < (1 + epsilon)b + beta, where beta is the vector of row sums beta_i = sum_j B_ij. Here m denotes the number of rows of A. This gives an O(ln 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 O(ln(max_j sum_i A_ij)) since 1982. CIP contains the set cover problem as a special case, so O(ln m)-approximation is the best possible unless P=NP.

Preliminary version appeared in IEEE Symposium on Foundations of Computer Science (2001). To appear in Journal of Computer and System Sciences

Cited by in corpus (11)

• On Column-restricted and Priority Covering Integer Programs
• Distributed algorithms for covering, packing and maximum weighted matching
• Greedy D-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• Computing an Approximately Optimal Agreeable Set of Items
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• An exact algorithm for the weighed mutually exclusive maximum set cover problem
• On Approximating Partial Set Cover and Generalizations
• A near-linear time minimum Steiner cut algorithm for planar graphs
• An exact algorithm with the time complexity of $O^{\ast }(1.299^m)$ for the weighed mutually exclusive set cover problem
• Approximate Deadline-Scheduling with Precedence Constraints
• Online Multi-Commodity Flow with High Demands