複数の部分集合の合計

多重部分集合和問題は、コンピュータサイエンスおよびオペレーションズリサーチにおける最適化問題である。これは部分集合和問題の一般化である。この問題への入力は多重集合である。${\displaystyle S}$n個の整数と、部分集合の数を表す正の整数mからなる集合。目標は、入力された整数からm個の部分集合を構築することです。この問題にはいくつかのバリエーションがあります。

• 最大和MSSP：1,..., mの各部分集合jに対して、容量Cjが存在する_。目標は、すべての部分集合の合計を可能な限り大きくし、各部分集合jの合計が最大でCjとなるようにすることである_。^{[ 1 ]}
• 最大最小 MSSP (ボトルネック MSSPまたはBMSSPとも呼ばれる): ここでも各サブセットには容量がありますが、今度は最小サブセットの合計をできるだけ大きくすることが目標です。^{[ 1 ]}
• 公平なSSP：サブセットには固定容量はありませんが、各サブセットは異なる人に属します。各人の効用は、その人のサブセットに含まれるアイテムの合計です。目標は、最大最小アイテム割り当てなどの、与えられた公平性の基準を満たすサブセットを構築することです。

mが変数（入力の一部）である場合、 3分割からの還元により、どちらの問題も強いNP困難となります。これは、P=NPでない限り、完全多項式時間近似スキーム（FPTAS）が存在しないことを意味します。

m = 2の場合でも、P = NP でない限り、問題には FPTAS は存在しません。これは、等濃度分割問題(EPART)からの還元によって示すことができます。

• 目標合計がTである EPART のインスタンスa ₁ ,..., a _nが与えられたとき、両方のサブセットに対して目標合計 ( n +1) Tである MSSP のインスタンス 2 T + a ₁ , ..., 2 T + a _{n を}構築します。
• EPARTの解は2つの部分から構成され、それぞれの部分はn /2個の要素を持ち、その合計はTとなる。これは、MSSPの2つのバリアントの最適解、すなわち合計が( n +1) Tとなる2つの部分集合に対応し、これは可能な限り最大の値である。同様に、MSSPの各最適解はEPARTの解に対応する。
• MSSPの最適解でない解では、少なくとも1つのアイテムが未割り当てのまま残るため、その合計は最大で2 nT、最小値は最大でnTとなります。どちらのバリアントでも、近似比は最大で${\displaystyle 1-1/(n+1)}$。
• したがって、どんな${\displaystyle \epsilon <1/(n+1)}$近似比を持つ任意のアルゴリズム${\displaystyle (1-\epsilon )}$最適解が存在する場合は、それを見つけなければならない。
• FPTASがあれば、例えば次のようなアルゴリズムが得られます。${\displaystyle \epsilon =1/(n+2)}$実行時間はnの多項式です。このアルゴリズムは、EPART をnの多項式時間で解くために使用できます。ただし、P=NP でない限り、これは不可能です。

以下の近似アルゴリズムが知られています: ^{[ 1 ]}

• 最大和MSSPの場合、変数mについて：
  • PTASは、O( m+n )の時間で実行されます。${\displaystyle \epsilon }$固定されています。実行時間は少なくとも指数関数的です。${\displaystyle 1/\epsilon ^{2}}$そして著者らはそれを非現実的だと考えている。
  • 部分集合の容量が異なる場合の、より一般的なPTAS。^{[ 2 ]}
  • O( m ² n )の時間で実行される 3/4 近似アルゴリズム。^{[ 3 ]}
• 最大最小MSSPの場合：
  • 変数mの場合: 2/3 近似、時間 O( n log n )。P=NP ( 3 分割からの還元による)でない限り、これ以上の近似は不可能。
  • 固定されたm : PTASで、時間内に実行${\displaystyle O(n^{2m/\epsilon })}$。
  • 固定数の異なる入力値を持つPTAS（レンストラのアルゴリズムを使用）。

公平部分集合和問題^{[ 4 ]}（FSSP）は、部分集合が選択された後、その項目が2人以上のエージェントに割り当てられるSSPの一般化です。各エージェントの効用は、そのエージェントに割り当てられた項目の重みの合計に等しくなります。目標は、効用プロファイルが平等主義ルールや比例公平ルールなどの公平性の基準を満たすことです。この問題には2つのバリエーションがあります。

• 共有アイテム: 各アイテムはすべてのエージェントに割り当てることができます。この設定は、同一の評価値による公平なアイテム割り当て(各アイテムの値はすべてのエージェントで同じで、アイテムの重みに等しい) に似ていますが、アイテムの合計重量に対する追加の容量制約があります。例として、アイテムの重みが 3、5、7、9 で、容量が 15 であるとします。すると、考えられる割り当てには、( {3、5、7}、{} ); ( {3、5}、{7} ); ( {5}、{3、7} ); ( {5}、{9} ) などがあります。これらの割り当てのうち、最大最小基準を満たすのは ( {3、5}、{7} ) です。
• 個別アイテム：各エージェントごとに、そのエージェントのみに割り当てられる個別のアイテムセットがあります。この設定は、予算を複数のプロジェクトに割り当てる必要があり、各プロジェクトがそれぞれ固有のエージェントに属する場合に有効です。

どちらのバリアントもNP困難です。ただし、エージェントが2人いる場合、すべてのパレート最適解を列挙するための擬似多項式時間アルゴリズムが存在します。 ^{[ 5 ]}

• 共有アイテムの場合：2次元配列を定義します${\displaystyle Q}$そのため${\displaystyle Q(w_{1},w_{2})={\text{true}}}$エージェントiに合計重みw _iを与える解が存在する場合に限る。可能なすべての効用プロファイルを列挙することは可能であり、${\displaystyle O(n\cdot c^{2})}$ここで、nはアイテムの数、cはアイテムの最大サイズである。
• 個別の項目については、各エージェントjに対して動的配列を定義します。${\displaystyle Q_{j}}$、したがって${\displaystyle Q_{j}(w)={\text{true}}}$エージェントjに合計重量wを与える解が存在する場合に限る。各配列${\displaystyle Q_{j}}$エージェントjの個々のアイテムを使用して別々に構築できます。次に、2 つの配列を反対方向に走査して、パレートフロンティア内のすべての割り当てを列挙できます。実行時間は${\displaystyle O(n\cdot c)}$。

Nicosia、Pacifici、Pferschyは、公平性の価格、すなわち、効用の合計最大値と、公平な解決策における効用の合計最大値との比率を研究している。

• 共有アイテムの場合：最大最小公平性の公平性の価格は無制限です。たとえば、値が 1、e、e、eの 4 つのアイテムがあり、 e > 0の小さな値があるとします。最大合計は 1 で、これは、一方のエージェントに値 1 のアイテムを与え、もう一方のエージェントには何も与えないことで達成されます。しかし、最大最小割り当てでは、各エージェントに少なくともe の値を与えるため、合計は最大で 3 eでなければなりません。したがって、POF は 1/(3 e ) となり、無制限です。
• アリスは値1とe（ただしeは0より大きい小さな値）の2つのアイテムを持っています。ジョージは値eの2つのアイテムを持っています。容量は1です。最大合計は1で、これはアリスに値1のアイテムを与え、ジョージには何も与えないことで達成されます。しかし、最大最小割り当てでは両方のエージェントに値eが与えられます。したがって、POFは1/(2e)となり、これは無制限です。
• 個別のアイテムの場合：最大最小公平性の公平性の価格は無制限です。たとえば、アリスが値 1 とeの 2 つのアイテムを持っているとします ( e > 0の小さな値)。ジョージが値eの 2 つのアイテムを持っています。容量は 1 です。最大合計は 1 です。これは、アリスが値 1 のアイテムを取得し、ジョージが何も取得しない場合です。しかし、最大最小割り当てでは、両方のエージェントに値eが与えられます。したがって、POF は 1/(2 e ) となり、無制限です。

どちらの場合も、アイテムの値が何らかの定数aによって制限されている場合、POF はaの関数によって制限されます。^{[ 5 ]}

複数ナップサック問題（MKP）は、最大和MSSPとナップサック問題の一般化です。この問題では、 m個のナップサックとn個のアイテムがあり、各アイテムには値と重量があります。目標は、 m個のナップサックにできるだけ多くの価値を詰め込み、各ナップサックの総重量がその容量以下になるようにすることです。

• 最大和MSSPは、各項目の値がその重みと等しいというMKPの特殊なケースである。
• ナップサック問題は、m = 1 の場合の MKP の特殊なケースです。
• 部分集合和問題は、各項目の値がその重みと等しく、かつm =1であるMKPの特殊なケースである。

MKPは多項式時間近似スキームを採用している。^{[ 6 ]}