Set covering is an optimization problem that nicely models many
problems of combinatorics and resource selection. Here is the idea: given a set *S*
and a set *P* of subsets *A*
_{1} to *A _{n}
* of

As an example, imagine trying to form a team from a large set of
candidate players, each with a certain set of skills. The goal is to
form the smallest team possible possessing a certain set of skills
overall. That is, for any skill required by the team as a whole, at
least one player on the team must possess the skill. Let
*S* be the skills that must be present on the team,
and let *P* be the sets of skills possessed by
various candidate players. The various player skill sets in
*P* that are placed in set *C*
together must cover all of the skills in set *S*.
But remember, we must select as few players as possible.

The algorithm presented here for set covering is an
approximation algorithm (see Chapter
1). It does not always obtain the best solution, but it does
come within a logarithmic bound. The algorithm works by repeatedly
picking a set from *P* that covers the most members
not yet covered in *S*. In other words, it tries to
cover as much of *S* as it can as early as it can.
Thus, the algorithm is greedy (see Chapter 1). As each set is selected
from *P*, it is removed, and its members are removed ...

Start Free Trial

No credit card required