Set packing

<h2 id="integer-linear-program-formulation">Integer linear program formulation</h2>
<p>The maximum set packing problem can be formulated as the following <a href="/facts/Integer_linear_program/MDaaadoA">integer linear program</a>.
</p>
<table><tbody><tr><td>maximize</td><td>                              ∑                      S            ∈                                          S                                                              x                      S                                {\displaystyle \sum _{S\in {\mathcal {S}}}x_{S}}  </td><td></td><td>(maximize the total number of subsets)</td></tr><tr><td>subject to</td><td>                              ∑                      S            :            e            ∈            S                                    x                      S                          ⩽        1              {\displaystyle \sum _{S\colon e\in S}x_{S}\leqslant 1}  </td><td>for all                     e        ∈                              U                                {\displaystyle e\in {\mathcal {U}}}  </td><td>(selected sets have to be pairwise disjoint)</td></tr><tr><td></td><td>                              x                      S                          ∈        {        0        ,        1        }              {\displaystyle x_{S}\in \{0,1\}}  </td><td>for all                     S        ∈                              S                                {\displaystyle S\in {\mathcal {S}}}  .</td><td>(every set is either in the set packing or not)</td></tr></tbody></table>
<h2 id="complexity">Complexity</h2>
<p>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 <a href="/facts/Maximum_clique_problem/cVVBNP08">maximum clique problem</a>; in particular, it cannot be approximated within any constant factor.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> The best known algorithm approximates it within a factor of 
  
    
      
        O
        (
        
          
            
              |
            
            
              
                U
              
            
            
              |
            
          
        
        )
      
    
    {\displaystyle O({\sqrt {|{\mathcal {U}}|}})}
  
.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> The weighted variant can also be approximated as well.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="packing-sets-with-a-bounded-size">Packing sets with a bounded size</h2>
<p>The problem does have a variant which is more tractable. Given any positive integer <i>k</i>≥3, the <i>k</i>-set packing problem is a variant of set packing in which each set contains at most <i>k</i> elements.
</p><p>When <i>k</i>=1, the problem is trivial. When <i>k</i>=2, the problem is equivalent to finding a <a href="/facts/Maximum_cardinality_matching/oKaChmBt">maximum cardinality matching</a>, which can be solved in polynomial time.
</p><p>For any <i>k</i>≥3, the problem is NP-hard, as it is more general than <a href="/facts/3-dimensional_matching/WFr6DxFj">3-dimensional matching</a>. However, there are <a href="/facts/Constant-factor_approximation_algorithms/ggqAJ3A3">constant-factor approximation algorithms</a>:
</p>
<ul><li>Cygan<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> presented an algorithm that, for any ε>0, attains a (<i>k</i>+1+ε)/3 approximation. The run-time is polynomial in the number of sets and elements, but doubly-exponential in 1/ε.</li>
<li>Furer and Yu<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> presented an algorithm that attains the same approximation, but with run-time singly-exponential in 1/ε.</li></ul>
<h2 id="packing-sets-with-a-bounded-degree">Packing sets with a bounded degree</h2>
<p>In another more tractable variant, if no element occurs in more than <i>d</i> of the subsets, the answer can be approximated within a factor of <i>d</i>. This is also true for the weighted version.
</p>
<h2 id="related-problems">Related problems</h2>
<h3>Equivalent problems</h3>
<p><a href="/facts/Hypergraph_matching/3tt40LSh">Hypergraph matching</a> is equivalent to set packing: the sets correspond to the hyperedges.
</p><p>The <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> problem is also equivalent to set packing – there is a one-to-one polynomial-time reduction between them:
</p>
<ul><li>Given a set packing problem on a collection 
  
    
      
        
          
            S
          
        
      
    
    {\displaystyle {\mathcal {S}}}
  
, build a graph where for each set 
  
    
      
        S
        ∈
        
          
            S
          
        
      
    
    {\displaystyle S\in {\mathcal {S}}}
  
 there is a vertex 
  
    
      
        
          v
          
            S
          
        
      
    
    {\displaystyle v_{S}}
  
, and there is an edge between 
  
    
      
        
          v
          
            S
          
        
      
    
    {\displaystyle v_{S}}
  
 and 
  
    
      
        
          v
          
            T
          
        
      
    
    {\displaystyle v_{T}}
  
 iff 
  
    
      
        S
        ∩
        T
        ≠
        ∅
      
    
    {\displaystyle S\cap T\neq \varnothing }
  
. Every independent set of vertices in the generated graph corresponds to a set packing in 
  
    
      
        
          
            S
          
        
      
    
    {\displaystyle {\mathcal {S}}}
  
.</li>
<li>Given an independent vertex set problem on a graph 
  
    
      
        G
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G(V,E)}
  
, build a collection of sets where for each vertex 
  
    
      
        v
      
    
    {\displaystyle v}
  
 there is a set 
  
    
      
        
          S
          
            v
          
        
      
    
    {\displaystyle S_{v}}
  
 containing all edges adjacent to 
  
    
      
        v
      
    
    {\displaystyle v}
  
. Every set packing in the generated collection corresponds to an independent vertex set in 
  
    
      
        G
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G(V,E)}
  
.</li></ul>
<p>This is also a bidirectional <a href="/facts/PTAS_reduction/ID1hKLk9">PTAS reduction</a>, and it shows that the two problems are equally difficult to approximate.
</p><p>In the special case when each set contains at most <i>k</i> elements (the <i>k-set packing problem</i>), the intersection graph is (<i>k</i>+1)-<a href="/facts/Claw-free_graph/P5FLH3uz">claw-free</a>. This is because, if a set intersects some <i>k</i>+1 sets, then at least two of these sets intersect, so there cannot be a (<i>k</i>+1)-claw. So Maximum Independent Set in claw-free graphs<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> can be seen as a generalization of Maximum <i>k</i>-Set Packing.
</p>
<h3>Special cases</h3>
<p><a href="/facts/Matching_(graph_theory)/s0pUJ7hd">Graph matching</a> is a special case of set packing in which the size of all sets is 2 (the sets correspond to the edges). In this special case, a maximum-size matching can be found in polynomial time.
</p><p><a href="/facts/3-dimensional_matching/WFr6DxFj">3-dimensional matching</a> is a special case in which the size of all sets is 3, and in addition, the elements are partitioned into 3 colors and each set contains exactly one element of each color. This special case is still NP-hard, though it has better constant-factor approximation algorithms than the general case.
</p>
<h3>Other related problems</h3>
<p>In the <a href="/facts/Set_cover_problem/MVzyBYs1">set cover problem</a>, we are given a family 
  
    
      
        
          
            S
          
        
      
    
    {\displaystyle {\mathcal {S}}}
  
 of subsets of a universe 
  
    
      
        
          
            U
          
        
      
    
    {\displaystyle {\mathcal {U}}}
  
, and the goal is to determine whether we can choose <i>t</i> sets that together contain every element of 
  
    
      
        
          
            U
          
        
      
    
    {\displaystyle {\mathcal {U}}}
  
.  These sets may overlap. The optimization version finds the minimum number of such sets. The maximum set packing need not cover every possible element.
</p><p>In the <a href="/facts/Exact_cover/C7QcbDcN">exact cover</a> problem, every element of 
  
    
      
        
          
            U
          
        
      
    
    {\displaystyle {\mathcal {U}}}
  
 should be contained in <i>exactly one</i> of the subsets. Finding such an exact cover is an <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problem, even in the special case in which the size of all sets is 3 (this special case is called exact 3 cover or X3C). However, if we create a <a href="/facts/Singleton_set/LtNVfujT">singleton set</a> for each element of <i>S</i> and add these to the list, the resulting problem is about as easy as set packing.
</p><p>Karp originally showed set packing NP-complete via a reduction from the <a href="/facts/Clique_problem/cVVBNP08">clique problem</a>.
</p>
<p class="note">See also: <a href="/facts/Packing_in_a_hypergraph/yTMhTb5q">Packing in a hypergraph</a></p>
<h2 id="notes">Notes</h2>

<ul><li>"<a href="https://xlinux.nist.gov/dads/HTML/setpacking.html">set packing</a>". <i>Dictionary of Algorithms and Data Structures</i>, editor Paul E. Black, <i>National Institute of Standards and Technology.</i> Note that the definition here is somewhat different.</li>
<li>Steven S. Skiena. "<a href="http://www3.cs.stonybrook.edu/~algorith/files/set-packing.shtml">Set Packing</a>". <i>The Algorithm Design Manual</i>.</li>
<li>Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, <a href="/facts/Marek_Karpinski/XPxNRbPA">Marek Karpinski</a> and <a href="/facts/Gerhard_J._Woeginger/beUa9kJr">Gerhard Woeginger</a>. "<a href="https://www.csc.kth.se/~viggo/wwwcompendium/node144.html">Maximum Set Packing</a>". <a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/"><i>A compendium of NP optimization problems</i></a>. Last modified March 20, 2000.</li>
<li><a href="/facts/Michael_R._Garey/xuSLYs90">Michael R. Garey</a> and <a href="/facts/David_S._Johnson/kGSBxucb">David S. Johnson</a> (1979). <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss"><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i></a>. W.H. Freeman. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7167-1045-5. A3.1: SP3, pg.221.</li>
<li><a href="/facts/Vijay_Vazirani/QzVR2f9n">Vazirani, Vijay V.</a> (2001). <i>Approximation Algorithms</i>. Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-65367-7.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml">[1]</a>: A Pascal program for solving the problem. From <i>Discrete Optimization Algorithms with Pascal Programs</i> by MacIej M. Syslo, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-13-215509-5.</li>
<li><a href="http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm">Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination</a></li>
<li><a href="https://web.archive.org/web/20101226041147/http://www.phpqa.in/2010/10/solving-packaging-problem-in-php.html">Solving packaging problem in PHP</a></li>
<li><a href="https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf">Optimizing Three-Dimensional Bin Packing</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "On the complexity of approximating k-set packing", Computational Complexity, 15 (1): 20–39, CiteSeerX 10.1.1.352.5754, doi:10.1007/s00037-006-0205-6, MR 2226068, S2CID 1858087. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within 
  
    
      
        O
        (
        
          n
          
            1
            −
            ϵ
          
        
        )
      
    
    {\displaystyle O(n^{1-\epsilon })}
  
 unless NP ⊂ ZPP." <a href="/w/index.php?title=Computational_Complexity_(journal)&action=edit&redlink=1" target="_blank">/w/index.php?title=Computational_Complexity_(journal)&action=edit&redlink=1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Independent sets with domination constraints. 25th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 1443. Springer-Verlag. pp. 176–185. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Halldórsson, Magnus M. (1999). Approximations of weighted independent set and hereditary subset problems. 5th Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 1627. Springer-Verlag. pp. 261–270. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Cygan, Marek (October 2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. arXiv:1304.1424. doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646. <a href="978-0-7695-5135-7" target="_blank">978-0-7695-5135-7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Fürer, Martin; Yu, Huiwen (2014). "Approximating the k-set packing problem by local improvements". In Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (eds.). Combinatorial Optimization. Lecture Notes in Computer Science. Vol. 8596. Cham: Springer International Publishing. pp. 408–420. doi:10.1007/978-3-319-09174-7_35. ISBN 978-3-319-09174-7. S2CID 15815885. <a href="978-3-319-09174-7" target="_blank">978-3-319-09174-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Neuwohner, Meike (2021). "An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs". In Bläser, Markus; Monmege, Benjamin (eds.). 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16–19, 2021, Saarbrücken, Germany (Virtual Conference). LIPIcs. Vol. 187. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 53:1–53:20. arXiv:2106.03545. doi:10.4230/LIPICS.STACS.2021.53. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Set packing open-in-new

Set packing