Next: String Matching Up: Set and String Problems Previous: Set Cover

## Set Packing

Input description: A set of subsets of the universal set .

Problem description: What is the largest number of mutually disjoint subsets from S?

Discussion: Set packing problems arise in partitioning applications, where we need to partition elements under strong constraints on what is an allowable partition. The key feature of packing problems is that no elements are permitted to be covered by more than one set. Consider the problem of finding the maximum independent set in a graph G, discussed in Section . We seek a large subset of vertices such that each edge is adjacent to at most one of the selected vertices. To model this as set packing, let the universal set consist of all edges of G, and subset consist of all edges incident on vertex . Any set packing corresponds to a set of vertices with no edge in common, in other words, an independent set.

Scheduling airline flight crews to airplanes is another application of set packing. Each airplane in the fleet needs to have a crew assigned to it, consisting of a pilot, copilot, and navigator. There are constraints on the composition of possible crews, based on their training to fly different types of aircraft, as well as any personality conflicts. Given all possible crew and plane combinations, each represented by a subset of items, we need an assignment such that each plane and each person is in exactly one chosen combination. After all, the same person cannot be on two different planes, and every plane needs a crew. We need a perfect packing given the subset constraints.

Set packing is used here to represent a bunch of problems on sets, all of which are NP-complete and all of which are quite similar:

• Must every element from the universal set appear in one selected subset? - In the exact cover problem, we seek some collection of subsets such that each element is covered exactly once. The airplane scheduling problem above has the flavor of exact covering, since every plane and crew has to be employed.

Unfortunately, exact cover is similar to that of Hamiltonian cycle in graphs. If we really must cover all the elements exactly once, and this existential problem is NP-complete, then all we can do is exponential search. This will be prohibitive unless there are so many solutions that we will stumble upon one quickly.

Things will be far better if we can be content with a partial solution, say by adding each element of U as a singleton subset of S. Thus we can expand any set packing into an exact cover by mopping up the unpacked elements of U with singleton sets. Now our problem is reduced to finding a minimum-cardinality set packing, which can be attacked via heuristics, as discussed below.

• What is the penalty for covering elements twice? - In set cover (see Section ), there is no penalty for elements existing in many selected subsets. In pure set packing, any such violation is forbidden. For many such problems, the truth lies somewhere in between. Such problems can be approached by charging the greedy heuristic more to select a subset that contains previously covered elements than one that does not.

The right heuristics for set packing are greedy, and similar to those of set cover (see Section ). If we seek a packing with many sets, then we repeatedly select the smallest subset, delete all subsets from S that clash with it, and repeat. If we seek a packing with few subsets, we do the same but always pick the largest possible subset. As usual, augmenting this approach with some exhaustive search or randomization (in the form of simulated annealing) is likely to yield better packings at the cost of additional computation.

Implementations: Since set cover is a more popular and more tractable problem than set packing, it might be easier to find an appropriate implementation to solve the cover problem. Many such implementations should be readily modifiable to support certain packing constraints.

Pascal implementations of an exhaustive search algorithm for set packing, as well as heuristics for set cover, appear in [SDK83]. See Section for details on ftp-ing these codes.

Notes: An excellent exposition on algorithms and reduction rules for set packing is presented in [SDK83], including the airplane scheduling application discussed above. Survey articles on set packing include [BP76].

Related Problems: Independent set (see page ), set cover (see page ).

Next: String Matching Up: Set and String Problems Previous: Set Cover

Algorithms
Mon Jun 2 23:33:50 EDT 1997