Set Covering

More formally, given a universe

\mathcal{U}

and a collection

\mathcal{S}

of subsets of

\mathcal{U}

,
a set cover is a subcollection

\mathcal{C}\subseteq\mathcal{S}

of sets whose union is

\mathcal{U}

. In the set cover Decision Problem , the input is a pair

(\mathcal{U},\mathcal{S})

and an integer

k

; the question is whether
there is a set cover of size

k

or less. In the set cover Optimization Problem , the input is a pair

(\mathcal{U},\mathcal{S})

, and the task is to find a set cover which uses the fewest sets.

The decision version of set cover is NP Complete , and the optimization version of set cover is NP Hard .

Set cover is exactly equivalent to the Hitting Set problem. It is easy to see this by observing that an instance of set cover can
be viewed as an arbitrary Bipartite Graph , with sets represented by vertices on the left, the universe represented by vertices on the
right, and edges representing the inclusion of elements in sets. The task is then to find a minimum subset of left-vertices which cover all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

The set cover problem can be seen as a finite version of the notion of Compactness in Topology , where the elements of certain infinite families of sets can be covered by choosing only finitely many of them.

Greedy algorithm

The greedy algorithm for set cover chooses sets according to one rule: at each stage, choose the set which contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of

H(s)

, where

s

is the size of the largest set and

H(n)

is the

n

-th Harmonic Number :

:

H(n) = \sum_{k=1}^{n} rac{1}{k} \approx \ln{n}

There is a standard example on which the greedy algorithm achieves an approximation ratio of

\log_2(n)/2

.
The universe consists of

n=2^{(k+1)}-2

elements. The set system consists of

k

pairwise disjoint sets

S_1,\ldots,S_k

with sizes

2,4,8,\ldots,2^k

respectively, as well as two additional disjoint sets

T_0,T_1

,
each of which contains half of the elements from each

S_i

. On this input, the greedy algorithm takes the sets

S_k,\ldots,S_1

, in that order, while the optimal solution consists only of

T_0

and

T_1

.
An example of such an input for

k=3

is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover
(see Inapproxibability Results below), under plausible complexity assumptions.

Low-frequency systems

If each element occurs in at most

f

sets, then a solution can be found in polynomial time which approximates the
optimum to within a factor of

f

. The algorithm formulates the set cover instance as an Integer Program , which is
relaxed to a Linear Program . The resulting linear program can be solved in polynomial time (e.g. using the Ellipsoid Algorithm ), and the solutions are rounded to obtain an approximate integral solution.

Inapproximability results

Lund and Yannakakis (1994) showed that set cover cannot be approximated in polynomial time to within a factor of

(\log_2{n})/2\approx{}0.72\ln{n}

, unless NP has quasi-polynomial time algorithms. Feige (1998)
improved this lower bound to

(1-o(1))\cdot\ln{n}

under the same assumptions, which essentially matches
the approximation ratio achieved by the greedy algorithm. Alon, Moshkovitz, and Safra established a lower bound
of

c\cdot\ln{n}

, where

c

is a constant, under the weaker assumption that P

ot=

NP.

Related problems are Vertex Cover , Set Packing , and Edge Cover .

REFERENCES

Noga Alon , Dana Moshkovitz , and Muli Safra . ''Algorithmic construction of sets for k-restrictions''. ACM Transactions on Algorithms, to appear.

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . '' Introduction To Algorithms '', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 35.3, The set-covering problem, pp.1033–1038.

Uriel Feige . ''A Threshold of $\ln{n}$ for Approximating Set Cover''. Journal of the ACM (JACM), v.45 n.4, p.634 - 652, July 1998.

Carsten Lund and Mihalis Yannakakis . ''On the hardness of approximating minimization problems''. Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994

EXTERNAL LINKS

Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination

Information About ™

Set Covering

Information About ^{^™}