セット梱包

セットパッキングは、計算複雑性理論と組合せ論における古典的なNP 完全問題であり、カープの 21 の NP 完全問題のうちの 1 つです。有限集合SとSのサブセットのリストがあるとします。セットパッキング問題は、リスト内のいくつかのk 個のサブセットがペアで互いに素であるかどうか(つまり、そのうちの 2 つが要素を共有しないかどうか) を問うものです。

より正式には、宇宙とのサブセットの族が与えられたとき、パッキングは内のすべてのセットがペアごとに互いに素であるようなセットのサブファミリーです。パッキングのサイズは です。セットパッキング決定問題では、入力はペアと整数です。問題は、サイズ以上のセットパッキングがあるかどうかです。セットパッキング最適化問題では、入力はペア で、タスクは最も多くのセットを使用するセットパッキングを見つけることです。 ${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle |{\mathcal {C}}|}$${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$${\displaystyle t}$${\displaystyle t}$${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$

この問題は明らかにNPに属します。なぜなら、部分集合が与えられれば、それらが互いに素であることを多項式時間で簡単に検証できるからです。 ${\displaystyle t}$

問題の最適化バージョンである最大セットパッキングは、リスト内のペアワイズ分離セットの最大数を求めます。これは、パッキング問題のクラスに属する、整数線形計画法として自然に定式化できる最大化問題です。

最大セットパッキング問題は、次の整数線形計画法として定式化できます。

セットパッキング問題はNP完全であるだけでなく、その最適化バージョン（一般的な最大セットパッキング問題）は最大クリーク問題と同じくらい近似するのが難しいことが証明されています。特に、任意の定数倍で近似することはできません。^[1]最もよく知られているアルゴリズムは、これを 倍数で近似します。^[2]重み付きバリアントも同様に近似できます。^[3]${\displaystyle O({\sqrt {|{\mathcal {U}}|}})}$

この問題には、より扱いやすい変種があります。任意の正の整数k ≥ 3 が与えられた場合、kセット パッキング問題は、各セットに最大k個の要素が含まれるセット パッキングの変種です。

k =1の場合、問題は簡単です。k =2 の場合、問題は に一致する最大基数を見つけることと同等であり、多項式時間で解決できます。

任意のk ≥ 3に対して、この問題は3次元マッチングよりも一般的なのでNP困難である。しかし、定数係数近似アルゴリズムが存在する:

• Cygan ^{[4]は、任意のε>0に対して(} k +1+ε)/3近似を達成するアルゴリズムを提示した。実行時間はセットと要素の数に対して多項式であるが、1/εに対しては二重指数関数的である。
• FurerとYu ^[5]は、同じ近似値を達成するアルゴリズムを提示したが、実行時間は1/εの単指数関数であった。

より扱いやすい別のバリエーションでは、 d 個を超えるサブセットに要素が出現しない場合、答えはd倍以内で近似できます。これは加重バージョンにも当てはまります。

ハイパーグラフ マッチングはセット パッキングと同等です。セットはハイパーエッジに対応します。

独立集合問題も集合パッキングと同等です。両者の間には 1 対 1 の多項式時間縮約が存在します。

• コレクション 上のセットパッキング問題が与えられた場合、各セットに対して頂点 が存在し、との間には の場合に限り辺が存在するグラフを構築します。生成されたグラフ内のすべての独立した頂点セットは、 内のセットパッキングに対応します。${\displaystyle {\mathcal {S}}}$${\displaystyle S\in {\mathcal {S}}}$${\displaystyle v_{S}}$${\displaystyle v_{S}}$${\displaystyle v_{T}}$${\displaystyle S\cap T\neq \varnothing }$${\displaystyle {\mathcal {S}}}$
• グラフ 上の独立頂点集合問題が与えられた場合、各頂点に対して に隣接するすべての辺を含む集合が存在する集合のコレクションを構築します。生成されたコレクション内のすべての集合パッキングは、 内の独立頂点集合に対応します。${\displaystyle G(V,E)}$${\displaystyle v}$${\displaystyle S_{v}}$${\displaystyle v}$${\displaystyle G(V,E)}$

これも双方向PTAS 削減であり、2 つの問題を近似するのが同様に難しいことを示しています。

各集合に最大でk 個の要素が含まれる特殊なケース（k-集合パッキング問題）では、交差グラフは ( k +1)-クローフリーです。これは、集合がいくつかのk +1 個の集合と交差する場合、これらの集合のうち少なくとも 2 つは交差するため、( k +1)-クローは存在できないためです。したがって、クローフリーグラフの最大独立集合^{[6]は、最大}k-集合パッキングの一般化と見なすことができます。

グラフ マッチングは、すべてのセットのサイズが 2 である (セットはエッジに対応) セット パッキングの特殊なケースです。この特殊なケースでは、最大サイズのマッチングを多項式時間で見つけることができます。

3 次元マッチングは、すべてのセットのサイズが 3 で、さらに要素が 3 色に分割され、各セットに各色の要素が 1 つだけ含まれる特殊なケースです。この特殊なケースは、一般的なケースよりも優れた定数係数近似アルゴリズムを備えていますが、依然として NP 困難です。

集合被覆問題では、宇宙のサブセットの族が与えられ、のすべての要素を含むt個の集合を選択できるかどうかを判断することが目標です。これらの集合は重複している可能性があります。最適化バージョンでは、そのような集合の最小数を見つけます。最大集合パッキングでは、すべての可能な要素をカバーする必要はありません。 ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {U}}}$

完全被覆問題では、 のすべての要素は、サブセットの1 つに正確に含まれていなければなりません。このような完全被覆を見つけることは、すべてのセットのサイズが 3 である特殊なケースであっても、NP 完全問題です (この特殊なケースは、完全 3 被覆またはX3Cと呼ばれます)。ただし、 Sの各要素に対してシングルトン セットを作成し、これをリストに追加すると、結果として生じる問題はセット パッキングと同じくらい簡単になります。 ${\displaystyle {\mathcal {U}}}$

Karp はもともと、クリーク問題からの還元を通じて集合パッキングが NP 完全であることを示した。

• 「セットパッキング」。アルゴリズムとデータ構造の辞書、編集者 Paul E. Black、国立標準技術研究所。ここでの定義は多少異なることに注意してください。
• Steven S. Skiena. 「セットパッキング」。アルゴリズム設計マニュアル。
• Pierluigi Crescenzi、Viggo Kann、Magnús Halldórsson、Marek Karpinski、Gerhard Woeginger。「最大セットパッキング」。NP 最適化問題の概要。最終更新日 2000 年 3 月 20 日。
• Michael R. GareyとDavid S. Johnson (1979)。コンピュータと扱いにくさ: NP 完全性理論のガイド。WH Freeman。ISBN 978-0-7167-1045-5。A3.1: SP3、221ページ。
• ヴァジラニ、ビジェイ V. (2001)。近似アルゴリズム。スプリンガー・フェルラーク。ISBN 978-3-540-65367-7。

• [1]: 問題を解決するためのパスカルプログラム。MacIej M. Syslo著『Pascalプログラムによる離散最適化アルゴリズム』ISBN 0-13-215509-5より。 
• セットカバー、セットパッキング、勝者決定のための最適解を隠したベンチマーク
• PHP でのパッケージ化問題の解決
• 3次元ビンパッキングの最適化