A Greedy Heuristic for the Set-Covering Problem

TLDR

The set‑covering problem seeks a minimum‑cost binary vector \(x\) satisfying \(Ax \ge e\) for a binary matrix \(A\) and cost vector \(c\). The study compares the objective value of a simple greedy heuristic solution to the optimal value for the set‑covering problem. A greedy heuristic that iteratively selects columns to cover uncovered rows is employed to generate a feasible solution. The greedy solution’s cost is within a logarithmic factor of the optimum, bounded by the largest column sum of \(A\), and reduces to the Johnson–Lovász bound when all costs are equal.

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.