A Greedy Heuristic for the Set-Covering Problem

Abstract

Let A be a binary matrix of size m × n, let c T be a positive row vector of length n and let e be the column vector, all of whose m components are ones. The set-covering problem is to minimize c T x subject to Ax ≥ e and x binary. We compare the value of the objective function at a feasible solution found by a simple greedy heuristic to the true optimum. It turns out that the ratio between the two grows at most logarithmically in the largest column sum of A. When all the components of c T are the same, our result reduces to a theorem established previously by Johnson and Lovasz.