Tight Approximation Results for General Covering Integer Programs

Preprint
Publisher Website
Google Scholar
Abstract
A covering integer program is one whose coefficients are all non-negative and whose contraints are all ``greater-than'' constraints. Finding a solution is NP-hard (set cover is a special case); in fact finding a o(logm)-approximate solution is NP-hard. It was an open question just how much harder the problem is if multiplicity constraints (explained below) are also allowed. This paper gives an O(logm)-approximation algorithm for the problem with multiplicity constraints, thus answering the open question up to a constant factor. A prototypical example is the set-cover problem: given a family of sets, find a small collection of the sets so that each element is in a chosen set. A natural generalization is to give each element e a covering requirement c(e), meaning that e should be in at least c(e) of the chosen sets. In this setting, a multiplicity constraint says that a set s may be chosen at most some d(s) times. (Without multiplicity constraints, the natural formulation as an integer program allows arbitrarily many copies of each set to be chosen.)

This publication has 0 references indexed in Scilit: