Bitmap index: Difference between revisions

Revision as of 11:22, 15 January 2014

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 share an element).

More formally, given a universe $𝒰$ and a family $𝒮$ of subsets of $𝒰$ , a packing is a subfamily $𝒞 \subseteq 𝒮$ of sets such that all sets in $𝒞$ are pairwise disjoint, and the size of the packing is $| 𝒞 |$ . In the set packing decision problem, the input is a pair $(𝒰, 𝒮)$ and an integer $k$ ; the question is whether there is a set packing of size $k$ or more. In the set packing optimization problem, the input is a pair $(𝒰, 𝒮)$ , and the task is to find a set packing that uses the most sets.

The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time.

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]

Template:Covering-Packing Problem Pairs

Integer linear program formulation

The maximum set packing problem can be formulated as the following integer linear program.

maximize	$\sum_{S \in 𝒮} x_{S}$		(maximize the total number of subsets)
subject to	$\sum_{S : e \in S} x_{S} ⩽ 1$	for all $e \in 𝒰$	(selected sets have to be pairwise disjoint)
	$x_{S} \in {0, 1}$	for all $S \in 𝒮$ .	(every set is either in the set packing or not)

Examples

As a simple example, suppose your kitchen contains a collection of different food ingredients ( $𝒰$ ), and you have a cook-book with a collection of recipes ( $𝒮$ ). Each recipe requires a subset of the food ingredients. You want to prepare the largest possible collection of recipes from the cook-book. You are actually looking for a set-packing ( $𝒞$ ) on ( $𝒰, 𝒮$ ) - a collection of recipes whose sets of ingredients are pairwise disjoint.

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

Weighted version

There is a weighted version of the set packing problem in which each subset is assigned a real weight and it is this weight we wish to maximize: $\sum_{S \in 𝒮} w (S) \cdot x_{S}$

In our simple example above, we might weight the recipes according to the number of friends that love the resulting dishes, so that our dinner will please the largest number of friends.

This seems to make the problem harder, but most known results for the unweighted problem apply to the weighted problem as well.

Heuristics

The set packing problem may be hard for some k, but 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.

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 problemPotter or Ceramic Artist Truman Bedell from Rexton, has interests which include ceramics, best property developers in singapore developers in singapore and scrabble. Was especially enthused after visiting Alejandro de Humboldt National Park.; 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.

Equivalent problems

There is a one-to-one polynomial-time reduction between the independent set problem and the set packing problem:

Given a set packing problem on a collection $𝒮$ , create a graph where for each set $S \in 𝒮$ there is a vertex $v_{S}$ , and there is an edge between $v_{S}$ and $v_{T}$ iff $S \cap T \neq ϕ$ . Now every independent set of vertices in the generated graph corresponds to a set packing in $𝒮$ .
Given an independent vertex set problem on a graph $G (V, E)$ , create a collection of sets where for each vertex $v$ there is a set $S_{v}$ containing all edges adjacent to $v$ . Now every set packing in the generated collection corresponds to an independent vertex set in $G (V, E)$ .

This is also a bidirectional PTAS reduction, and it shows that the two problems are equally difficult to approximate.

Special cases

Matching and 3-dimensional matching 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.

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

Maximum Set Packing, Viggo Kann.
"set packing". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
Steven S. Skiena. "Set Packing". The Algorithm Design Manual. Last modified June 2, 1997.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems. Last modified March 20, 2000.
20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 A3.1: SP3, pg.221.
20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

External links

[1]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, ISBN 0-13-215509-5.
Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
Solving packaging problem in PHP

Template:Packing problem

↑ Template:Harvtxt

[1] Template:Harvtxt

[1]

@@ Line 1: / Line 1: @@
+'''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 sets|disjoint]] (in other words, no two of them share an element).
-I woke up the other day  and realized - I have been single for a little while today and following much bullying   [http://okkyunglee.com luke bryan shows] from pals I now locate myself signed-up for web dating. They guaranteed me that there are lots of regular, sweet and interesting individuals to meet, therefore the pitch is gone by here!<br>My pals and household are magnificent and spending some   [http://www.netpaw.org luke bryan live in concert] time together at tavern gigabytes or dinners is obviously critical. As I see that you can not have a nice dialogue   [http://www.cinemaudiosociety.org luke bryan to] using the sound I have never been in to nightclubs. I also have 2 unquestionably cheeky and very cute canines that are constantly excited to meet up new people.<br>I attempt to maintain as physically healthy as possible staying at the fitness center many times a week. I enjoy my sports and endeavor to play or see as numerous a possible. Being wintertime I'll regularly at [http://www.Thefreedictionary.com/Hawthorn+suits Hawthorn suits]. Note: Supposing that you would considered shopping an activity I really don't brain, I've experienced the carnage of wrestling matches at stocktake revenue.<br><br>Feel free to surf to my webpage - [http://lukebryantickets.hamedanshahr.com luke bryan t]
+More formally, given a universe <math>\mathcal{U}</math> and a family <math>\mathcal{S}</math> of subsets of <math>\mathcal{U}</math>,
+a ''packing'' is a subfamily <math>\mathcal{C}\subseteq\mathcal{S}</math> of sets such that all sets in <math>\mathcal{C}</math> are pairwise disjoint, and the size of the packing is <math>|\mathcal{C}|</math>. In the set packing [[decision problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math> and an integer <math>k</math>; the question is whether
+there is a set packing of size <math>k</math> or more. In the set packing [[optimization problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math>, and the task is to find a set packing that uses the most sets.
+The problem is clearly in [[NP (complexity)|NP]] since, given ''k'' subsets, we can easily verify that they are pairwise disjoint in [[P (complexity)|polynomial time]].
+The [[optimization problem|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 problem]]s, and its [[dual linear program]] is the [[set cover problem]].<ref>{{harvtxt|Vazirani|2001}}</ref>
+{{Covering-Packing Problem Pairs}}
+==Integer linear program formulation==
+The maximum set packing problem can be formulated as the following [[integer linear program]].
+{|
+| maximize
+| <math>\sum_{S \in \mathcal S}  x_S</math>
+|
+| (maximize the total number of subsets)
+|-
+| subject to
+| <math>\sum_{S\colon e \in S} x_S \leqslant 1 </math>
+| for all <math>e\in \mathcal U</math>
+| (selected sets have to be pairwise disjoint)
+|-
+|
+| <math>x_S \in \{0,1\}</math>
+| for all <math>S\in \mathcal S</math>.
+| (every set is either in the set packing or not)
+|}
+== Examples ==
+As a simple example, suppose your kitchen contains a collection of different food ingredients (<math>\mathcal{U}</math>), and you have a cook-book with a collection of recipes ( <math>\mathcal{S}</math>). Each recipe requires a subset of the food ingredients. You want to prepare the largest possible collection of recipes from the cook-book. You are actually looking for a set-packing (<math>\mathcal{C}</math>) on (<math>\mathcal{U},\mathcal{S}</math>) - a collection of recipes whose sets of ingredients are pairwise disjoint.
+As another 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.
+== Weighted version  ==
+There is a weighted version of the set packing problem in which each subset is assigned a real weight and it is this weight we wish to maximize: <math>\sum_{S \in \mathcal S} w(S) \cdot x_S</math>
+In our simple example above, we might weight the recipes according to the number of friends that love the resulting dishes, so that our dinner will please the largest number of friends.
+This seems to make the problem harder, but most known results for the unweighted problem apply to the weighted problem as well.
+== Heuristics ==
+The set packing problem may be hard for some ''k'', but 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.
+== 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]]{{Citation needed|date=July 2013}}; in particular, it cannot be approximated within any constant factor. The best known algorithm approximates it within a factor of <math>O(\sqrt{|S|})</math>. 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.
+== Equivalent problems ==
+There is a one-to-one polynomial-time reduction between the [[Independent set (graph theory)|independent set]] problem and the set packing problem:
+* Given a set packing problem on a collection <math>\mathcal{S}</math>, create a graph where for each set <math>S \in \mathcal{S}</math> there is a vertex <math>v_S</math>, and there is an edge between <math>v_S</math> and <math>v_T</math> iff <math>S \cap T \neq \phi</math>. Now every independent set of vertices in the generated graph corresponds to a set packing in <math>\mathcal{S}</math>.
+* Given an independent vertex set problem on a graph <math>G(V,E)</math>, create a collection of sets where for each vertex <math>v</math> there is a set <math>S_v</math> containing all edges adjacent to <math>v</math>. Now every set packing in the generated collection corresponds to an independent vertex set in <math>G(V,E)</math>.
+This is also a bidirectional [[PTAS reduction]], and it shows that the two problems are equally difficult to approximate.
+== Special cases ==
+[[Matching (graph theory)|Matching]] and [[3-dimensional matching]] 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.
+== Other 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.
+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]].
+See also: [[Packing in a hypergraph]].
+== Notes ==
+{{reflist}}
+== References ==
+* [http://www.nada.kth.se/~viggo/wwwcompendium/node144.html Maximum Set Packing], Viggo Kann.
+* "[http://www.nist.gov/dads/HTML/setpacking.html set packing]". ''Dictionary of Algorithms and Data Structures'', editor Paul E. Black, ''National Institute of Standards and Technology.'' Note that the definition here is somewhat different.
+* Steven S. Skiena. "[http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE202.HTM Set Packing]". ''The Algorithm Design Manual''. Last modified June 2, 1997.
+* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]] and Gerhard Woeginger. "[http://www.nada.kth.se/~viggo/wwwcompendium/node144.html Maximum Set Packing]". [http://www.nada.kth.se/%7Eviggo/wwwcompendium/ ''A compendium of NP optimization problems'']. Last modified March 20, 2000.
+* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A3.1: SP3, pg.221.
+* {{Cite book | last=Vazirani | first=Vijay V. | authorlink=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 | pages=}}
+== External links ==
+* [http://www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml]: A Pascal program for solving the problem. From ''Discrete Optimization Algorithms with Pascal Programs'' by MacIej M. Syslo, ISBN 0-13-215509-5.
+* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination]
+*[http://www.phpqa.in/2010/10/solving-packaging-problem-in-php.html Solving packaging problem in PHP]
+{{Packing problem}}
+[[Category:Combinatorics]]
+[[Category:NP-complete problems]]

Bitmap index: Difference between revisions

Revision as of 11:22, 15 January 2014

Contents

Integer linear program formulation

Examples

Weighted version

Heuristics

Complexity

Equivalent problems

Special cases

Other related problems

Notes

References

External links

Navigation menu

Bitmap index: Difference between revisions

Revision as of 11:22, 15 January 2014

Integer linear program formulation

Examples

Weighted version

Heuristics

Complexity

Equivalent problems

Special cases

Other related problems

Notes

References

External links

Navigation menu

Search