Mastering Algorithms with C

Set Example: Set Covering

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 ₁ to A_n of S, set C, which is composed of one or more sets from P, is said to cover S if each member in S is contained in at least one of the subsets in C; in addition, C contains as few sets from P as possible.

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 ...