複数の部分集合の合計

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

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

最大合計と最大最小 MSSP

mが変数（入力の一部）の場合、 3分割からの縮約により、どちらの問題も強NP困難となる。つまり、 P=NPでない限り、完全多項式時間近似法（FPTAS）は存在しない。

m =2の場合でも、P=NPでない限り、問題にはFPTASは存在しません。これは、等価基数分割問題（EPART） からの帰着によって示されます。

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

以下の近似アルゴリズムが知られている: [ 1 ]

  • 最大和MSSPの場合、変数mは次のようになります。
    • が固定されている場合、実行時間 O( m+n )で実行される PTAS 。実行時間は では少なくとも指数関数的であり、著者らは実用的ではないと考えている。ϵ{\displaystyle \epsilon }1/ϵ2{\displaystyle 1/\epsilon ^{2}}
    • サブセット容量が異なる場合のより一般的なPTAS。[ 2 ]
    • O( m2n )の時間で実行される3/4近似アルゴリズム。[ 3 ]
  • 最大最小MSSPの場合:

公平な部分集合和問題

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

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

どちらの変種もNP困難である。しかし、2つのエージェントが存在する場合、すべてのパレート最適解を列挙する擬多項式時間アルゴリズムが存在する。 [ 5 ]

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

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

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

参考文献

  1. ^ a b c Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). 「多重部分集合和問題」 . SIAM Journal on Optimization . 11 (2): 308– 319. doi : 10.1137/S1052623498348481 . ISSN  1052-6234 .
  2. ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-29). 「異なるナップサック容量を持つ多重部分集合和問題に対するPTAS」 . Information Processing Letters . 73 ( 3–4 ): 111– 118. doi : 10.1016/S0020-0190(00)00010-7 . ISSN 0020-0190 . 
  3. ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2003-03-01). 「複数部分集合和のための3/4近似アルゴリズム」 . Journal of Heuristics . 9 (2): 99– 111. doi : 10.1023/A:1022584312032 . ISSN 1572-9397 . S2CID 1120180 .  
  4. ^ Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). 「Brief Announcement: On the Fair Subset Sum Problem」 . Hoefer, Martin (ed.). Algorithmic Game Theory . Lecture Notes in Computer Science. Vol. 9347. Berlin, Heidelberg: Springer. pp.  309– 311. doi : 10.1007/978-3-662-48433-3_28 . ISBN 978-3-662-48433-3。
  5. ^ a b Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2017-03-16). 「有限資源の割り当てにおける公平性の代償」 . European Journal of Operational Research . 257 (3): 933– 943. arXiv : 1508.05253 . doi : 10.1016/j.ejor.2016.08.013 . ISSN 0377-2217 . S2CID 14229329 .  
  6. ^ Chandra ChekuriとSanjeev Khanna (2005). 「多重ナップサック問題に対するPTAS」SIAM Journal on Computing . 35 (3): 713– 728. CiteSeerX 10.1.1.226.3387 . doi : 10.1137/s0097539700382820 . 
「 https://en.wikipedia.org/w/index.php?title=Multiple_subset_sum&oldid=1321258610」より取得