Set Packing - Heuristics and Related Problems

Heuristics and Related Problems

Set packing is one among a family of problems related to covering or partitioning the elements of a set. One closely related problem is the set cover problem. Here, we are also given a set S and a list of sets, but the goal is to determine whether we can choose k sets that together contain every element of S. These sets may overlap. The optimization version finds the minimum number of such sets. The maximum set packing need not cover every possible element.

One advantage of the set packing problem is that even if it's hard for some k, it's not hard to find a k for which it is easy on a particular input. For example, we can use a greedy algorithm where we look for the set which intersects the smallest number of other sets, add it to our solution, and remove the sets it intersects. We continually do this until no sets are left, and we have a set packing of some size, although it may not be the maximum set packing. Although no algorithm can always produce results close to the maximum (see next section), on many practical inputs these heuristics do so.

The NP-complete exact cover problem, on the other hand, requires every element to be contained in exactly one of the subsets. Finding such an exact cover at all, regardless of size, is an NP-complete problem. However, if we create a singleton set for each element of S and add these to the list, the resulting problem is about as easy as set packing.

Karp originally showed set packing NP-complete via a reduction from the clique problem.

There is a weighted version of the set cover problem in which each subset is assigned a real weight and it is this weight we wish to maximize. In our example above, we might weight the ambassadors according to the populations of their countries, so that our announcement will reach the most people possible. This seems to make the problem harder, but as we explain below, most known results for the general problem apply to the weighted problem as well.