Set packing

Set packing

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.

Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them intersect). The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint.

The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list. It is a maximization problem that can be formulated naturally as an integer linear program, belongs to the class of packing problems, and its dual linear program is the set cover problem.[1]

Covering-packing dualities
Covering problems Packing problems
Minimum set cover Maximum set packing
Minimum vertex cover Maximum matching
Minimum edge cover Maximum independent set

Contents

Example

As a simple example, suppose you're at a convention of foreign ambassadors, each of which speaks English and also various other languages. You want to make an announcement to a group of them, but because you don't trust them, you don't want them to be able to speak among themselves without you being able to understand them. To ensure this, you will choose a group such that no two ambassadors speak the same language, other than English. On the other hand you also want to give your announcement to as many ambassadors as possible.

In this case, the elements of the set are languages other than English, and the subsets are the sets of languages spoken by a particular ambassador. If two sets are disjoint, those two ambassadors share no languages other than English. A maximum set packing will choose the largest possible number of ambassadors under the desired constraint. Although this problem is hard to solve in general, in this example a good heuristic is to choose ambassadors who only speak unusual languages first, so that not too many others are disqualified.

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.

Complexity

The set packing problem is not only NP-complete, but its optimization version (general maximum set packing problem ) has been proven as difficult to approximate as the maximum clique problem; in particular, it cannot be approximated within any constant factor. The best known algorithm approximates it within a factor of O(\sqrt{|S|}). The weighted variant can also be approximated this well.

However, the problem does have a variant which is more tractable: if we assume no subset exceeds k≥3 elements, the answer can be approximated within a factor of k/2 + ε for any ε > 0; in particular, the problem with 3-element sets can be approximated within about 50%. In another more tractable variant, if no element occurs in more than k of the subsets, the answer can be approximated within a factor of k. This is also true for the weighted version.

See also

  • Matching, 3-dimensional matching, and independent set are special cases of set packing. A maximum-size matching can be found in polynomial time, but finding a largest 3-dimensional matching or a largest independent set is NP-hard.
  • Packing in a hypergraph.

Notes

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Set packing — Le problème de set packing est un problème d optimisation combinatoire NP complet. Il peut être considéré comme une version particulière du problème du sac à dos multidimensionnel où les poids des objets sont égaux à 0 ou 1 et où les capacités du …   Wikipédia en Français

  • Packing — may refer to:In Mechanical engineering: * Packing, also known as an O ring or other type of Seal (mechanical), a term for a sealing material * Packing gland is a mechanical term for the groove in which a packing sits.In Mathematics: * Sphere… …   Wikipedia

  • Packing problem — Part of a series on Puzzles …   Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

  • set honey — закристаллизовавшийся мед honey packing plant установка для расфасовки меда honey flavor imitation имитация аромата меда crystallized honey закристаллизовавшийся мед granulated honey закристаллизовавшийся мед solid honey закристаллизовавшийся мед …   English-Russian travelling dictionary

  • Independent set (graph theory) — The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices …   Wikipedia

  • Circle packing theorem — Example of the circle packing theorem on K5, the complete graph on five vertices, minus one edge. The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane …   Wikipedia

  • Kakeya set — deltoid. At every stage of its rotation, the needle is in contact with the deltoid at three points: two endpoints (blue) and one tangent point (black).The needle s midpoint (red) describes a circle with diameter equal to half the length of the… …   Wikipedia

  • Reduced instruction set computer — The acronym RISC (pronounced risk ), for reduced instruction set computing, represents a CPU design strategy emphasizing the insight that simplified instructions which do less may still provide for higher performance if this simplicity can be… …   Wikipedia

  • To set the cart before the horse — Cart Cart (k[aum]rt), n. [AS. cr[ae]t; cf. W. cart, Ir. & Gael. cairt, or Icel. kartr. Cf. {Car}.] 1. A common name for various kinds of vehicles, as a Scythian dwelling on wheels, or a chariot. Ph[oe]bus cart. Shak. [1913 Webster] 2. A two… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”