Packing problem

From Glossary

Jump to: navigation, search

The set packing problem is the question, "Does a collection of sets contain at least LaTeX: K mutually disjoint subsets?" (LaTeX: K is a positive integer not greater than the number of sets given.) This is solvable in polynomial time if no set has more than 2 members. Otherwise, it has the NP-hard equivalent integer program: LaTeX: \textstyle \max \left \{ \sum_j x_j: Ax \le 1, x \in \left \{0, 1 \right \}^n\right\}, where LaTeX: x_j = 1 if element LaTeX: j is selected; else, LaTeX: x_j = 0. The matrix LaTeX: A has 0's and 1's, where the i-th row corresponds the i-th set to be packed: LaTeX: A_{(i, j)}=1 means element j is in set i; else, LaTeX: A_{(i, j)}=0. The constraint LaTeX: Ax \le 1 means that at most one element of each set can be selected. If the IP maximum is less than LaTeX: K-1, or if it equals LaTeX: K-1 = number of elements, the answer to the set packing problem is "No". Otherwise, let LaTeX: \textstyle x_1, \dots, x_{(K-1)} be among those elements selected (re-index, if necessary). Let LaTeX: S_i be all sets containing LaTeX: x_i. Due to the packing constraints, no selected element can be in two sets, so these are disjoint. The remaining set, LaTeX: S_K, is composed of all other elements LaTeX: \textstyle (x_K, \dots, x_n), and must be disjoint from the other sets, so the answer to the set packing question is "Yes" (and we can construct the disjoint subsets).

A special case is the node packing problem on a graph: find a set of nodes of maximum cardinality such that no node is incident with the same edge (or arc). In that case, every row of LaTeX: A has exactly two 1's, and this is sometimes called [1]egree-2 inequalities. Another special case is the bin packing problem.

The IP formulation has the natural extension: LaTeX: \textstyle \max \left \{ cx: Ax \le b, x \in \left \{0,1 \right \}^n \right \}, where LaTeX: \textstyle c \ge 0 and LaTeX: \textstyle b \ge 1. This allows up to LaTeX: b_i elements to be selected from the i-th set, and elements can be weighted by value LaTeX: (c).

Personal tools