マルチフィットアルゴリズム

コフマン、ゲイリー、ジョンソンは、以下の上限を証明する。$\displaystyle r_n}}$: ^{[ 1 ]}

• $\displaystyle r_{n}\leq 8/7\approx 1.14$n = 2 の場合。
• $\displaystyle r_{n}\leq 15/13\approx 1.15$n = 3 の場合。
• $\displaystyle r_{n}\leq 20/17\approx 1.176$n = 4,5,6,7の場合。
• $\displaystyle r_{n}\leq 122/100=1.22}$n ≥ 8のすべての場合。

MultiFitアルゴリズムでは、下限Lは常にSをn個のビンに詰め込むことが不可能な容量です。したがって、${\displaystyle L<r_{n}\cdot OPT(S,n)}$最初は、その違いは${\displaystyle UL}$は最大で sum( S ) / n であり、これは最大で${\displaystyle OPT(S,n)}$MultiFitアルゴリズムをk回繰り返すと、差は半分のk倍に縮小するので、${\displaystyle UL\leq (1/2)^{k}\cdot OPT(S,n)}$。 したがって、${\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}$したがって、MultiFit によって返されるスケジューリングのメイクスパンは最大で$\displaystyle r_{n}+(1/2)^{k}}$最適なメイクスパンの倍数。${\displaystyle k}$が十分に大きい場合、MultiFit の近似係数は任意に に近づけることができる。$\displaystyle r_n}}$これは最大で1.22です。

後の論文では、MultiFit のより詳細な分析が行われ、その近似比は最大で 6/5= 1.2であることを証明し^{[ 2 ]}、さらに後には最大で 13/11≈ 1.182であることを証明しました^{[ 3 ]}。この証明の元の証明ではいくつかのケースが見落とされていました。 ^{[ 4 ]}は完全でより簡単な証明を示しました。13/11 は改善できません。以下の下限を参照してください。^{[ 2 ]}

n = 4の場合：次の^{[ 5 ]}は、${\displaystyle r_{n}\geq 20/17}$これはタイトな構成です。入力は 9,7,6,5,5,4,4,4,4,4,4,4,4,4 です。これらは、容量 17 の 4 つのビンに次のように詰め込むことができます。

• 9、4、4
• 7、6、4
• 5、4、4、4
• 5、4、4、4

しかし、FFDをビン容量20未満で実行した場合、満杯になるビンは次のようになります。

• 9,7 [4は当てはまりません]
• 6,5,5 [4は入りません]
• 4,4,4,4 [4は入りません]
• 4,4,4,4
• 4

最初の4つのビンの合計はそれぞれ16なので、さらに4を入れることはできません。したがって、4つのビンでは不十分です。

n = 13の場合、次の^{[ 2 ]}は、${\displaystyle r_{n}\geq 13/11}$これはかなり窮屈です。入力は、容量66の13個のビンに以下のように詰め込むことができます。

• 40,13,13 {8回}
• 25,25,16 {3回}
• 25,24,17 {2回}

しかし、FFDをビン容量66*13/11 = 78より小さい値で実行した場合、満たされるビンは次のようになります。

• 40.25 {8回}
• 24、24、17
• 17、16、16、16
• 13、13、13、13、13（3回）
• 13

最初の13個のビンの合計は65なので、さらに13個を入れることはできません。したがって、13個のビンでは不十分です。

MultiFitは、マシンの処理速度が異なる場合がある均一マシンスケジューリングと呼ばれるより一般的な設定でも使用できます。 ^{[ 6 ]} 2台の均一マシンがある場合、近似係数は$\displaystyle {\sqrt {6}}/2}$MultiFitをLPTアルゴリズムと組み合わせると、比率は改善され、$\displaystyle {\sqrt {2}}+1/2}$。

最大合計（メイクスパン）を最小化するという二重の目標は、最小合計を最大化することです。Deuermeyer、Friesen、Langstonは、MultiFitにはこの問題に対する適切な近似係数がないと主張しています。^{[ 7 ]}

「MULTIFITを用いたメイクスパン問題の解法では、プロセッサが全く使用されない例を容易に作成できます。このような解法はメイクスパン問題には許容範囲内ですが、我々の問題には全く適していません_{（最小合計が0になるため） 。MULTIFITの改良版を考案すれば、我々の問題により適したものが見つかるかもしれませんが、} LPTよりも優れた最悪ケースの上限値を与えるものは見つかりませんでした。」

上限値$\displaystyle r_n}}$背理法によって証明される。任意の整数p ≥ qに対して、${\displaystyle r_{n}>p/q}$すると、( p / q )反例が存在し、それはインスタンスSとビンの数nとして定義され、

• Sは容量qのn個の容器に詰め込むことができる。
• FFD は、容量pのn個のビンにSを詰め込むことができません。

このような反例が存在する場合、最小の (p/q)-反例も存在します。これは、S内のアイテム数が最小で、ビンの数nが最小の ( p / q )-反例です。最小の(p/q) -反例では、FFD はS内の最後の (最小の) アイテムを除くすべてのアイテムを、容量pのn 個のビンに詰めます。最小の(p/q) -反例が与えられた場合、容量pのこれらのn 個のビン への (不完全な) FFD のパッキングをP ₁ ,..., P _nで表し、最小のアイテムが 1 つだけ含まれるビンを P _n+1で表し、容量qのn個のビンへの (完全な) 最適なパッキングをQ ₁ ,...,Q _nで表します。次の補題が証明できます。

• {Q _1,..., Q _{n } からの}k個の部分集合の和集合は、{P _1,..., P _{n+1 } からの}k個の部分集合の和集合によって支配されることはありません (「支配される」とは、支配される部分集合の各項目が、支配する部分集合のより小さい項目にマッピングされることを意味します)。そうでなければ、次のようにより小さい反例を得ることができます。[1] P _iのすべての項目を削除します。明らかに、不完全な FFD パッキングでは、n - k個のビンが必要になり、最小の項目 (またはビン全体) はまだパックされていません。[2] 最適なパッキング Q _iで、各項目をその支配する項目と交換します。これで、k個の部分集合 Q _{i は}大きくなります (おそらくqより大きい) が、他のすべてのn - k個の部分集合は小さくなります (特に、最大でqです)。したがって、P _iのすべての項目を削除した後、残りの項目は、最大でn - k個のサイズqのビンにパックできます。
• Q _1,..., Q _nのそれぞれには、少なくとも 3 つの項目が含まれています。そうでなければ、支配関係が成立し、前の補題により、より小さな反例を得ることができました。これは、[a] 1 つの項目を持つ各 Q _{i は}、その項目を含むP _jによって支配されます。[b] 2 つの項目xとyを持つ各 Q _iについて、xとyの両方が同じ P _jにある場合、 Q _{i はこの P j}によって支配されます。[c] x≥y と仮定すると、x はある P _jにあり、 y はその右側にある P _{kにあります。これは、y が P j}に収まらなかったことを意味します。しかし、x+y ≤ q です。これは、P _{j に}は項目 z ≥ y が含まれている必要があることを意味します。したがって、Q _{iは P j}によって支配されます。 [d] x≥y と仮定すると、x はある P _jにあり、 y はその左側にある P _kにあります。これは、前の項目 z ≥ x が存在する必要があることを意味します。したがって、Q _{iは P k}によって支配されます。
• P _1,..., P _nのそれぞれには、少なくとも 2 つの項目が含まれています。これは、P _iに 1 つの項目しか含まれていない場合、最後の (最小の) 項目がそこに収まらないことを意味するからです。つまり、この 1 つの項目は最適なバンドルの中で単独で存在しなければならず、前の補題と矛盾します。
• 最小のアイテムのサイズをsとします。すると${\displaystyle s>{\frac {n}{n-1}}(pq)}$証明：sは最初のn個の束に収まらないので、${\displaystyle sum(P_{i})+s>p}$、 それで${\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}$一方、すべてのアイテムは容量qのn個のビンに収まるので、${\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}$不等式を引くと${\displaystyle s>{\frac {n}{n-1}}(pq)}$。
• 各アイテムのサイズは最大で${\displaystyle q-2s}$これは、各最適ビン（容量q）に少なくとも3つのアイテムが含まれているためです。
• _{各ビン P 1,...,} P _n内のアイテムの合計は以下よりも大きい。${\displaystyle ps}$そうでなければ、最小のアイテムを追加することもできます。

上記の補題から、緩やかな上限を証明することは既に可能である。$\displaystyle r_{n}\leq 5/4=1.25$証明。S , n を最小の (5/4)-反例とする。上記の補題から、次のことが導かれる。

• ${\displaystyle s>{\frac {n}{n-1}}(5-4)>1}$最適な容量は4なので、最適なビンには4個以上のアイテムを入れることはできません。したがって、各最適なビンには最大3個のアイテムしか入れることができず、アイテムの総数は最大で3n個になります。
• 各アイテムのサイズは最大で${\displaystyle 4-2s}$、各FFDビンのサイズは${\displaystyle 5-s}$もしFFDビンに2つのアイテムしか含まれていない場合、その合計は最大で${\displaystyle 8-4s=5+(3-3s)-s<5-s}$つまり、FFDの各ビンには少なくとも3つのアイテムが含まれている必要がある。しかし、これはFFDがちょうどn個のビンを生成することを意味し、矛盾が生じる。

より厳密な境界を証明するには、最小の ( p / q )-反例の FFD パッキングを詳しく調べる必要があります。項目と FFD ビン P ₁、...、P _{n は}次のように呼ばれます。

• 通常アイテムとは、次のビン P _i+1が開かれる前に、いずれかのビン P _iに追加されたアイテムのことです。言い換えれば、通常アイテムとは、ビン P _{i内のアイテムのうち、} j > iのすべてのビン P _j内のアイテムの合計サイズ以上であるアイテムのことです。
• フォールバックアイテムとは、次のビン P _i+1が開かれた後に、いずれかのビン P _iに追加されるアイテムのことです。言い換えれば、フォールバックアイテムとは、P _{i内のアイテムのうち、P i+1}内の最大のアイテムよりも小さいアイテムのことです。
• 通常のkビンとは、 k個の通常のアイテムを含み、代替アイテムを含まないビンのことです。
• フォールバックkビンとは、 k個の通常アイテムといくつかのフォールバックアイテムを含むビンのことです。

以下の補題は、これらの定義とFFDの動作から直ちに導かれる。

• k ₁ < k ₂の場合、すべてのk _{1ビンはすべての}k ₂ビンの左側に配置されます。これは、すべてのビンの容量が同じであるため、より多くの通常のアイテムがビンに収まる場合、それらのアイテムはより小さくなければならず、したがって後から割り当てられる必要があるためです。
• _{P iが}kビンである場合、P _iのk個の通常の項目の合計は以下よりも大きい。$\displaystyle {\frac {k}{k+1}}\cdot p}$そうしないと、新しいゴミ箱を開ける前に別のアイテムを追加できてしまうからです。
• P _iと P _i+1が両方ともkビンである場合、P _{iの k 個の通常のアイテムの合計は、P i+1の}k個の通常のアイテムの合計以上になります(これは、アイテムが降順で並べられているためです)。
• 通常のkビンはすべて、フォールバックkビンの左側に配置されます。これは、すべてのビンの容量が同じであるため、フォールバックアイテムがビンに多く収まる場合は、フォールバックアイテムのサイズが小さくなり、割り当てが遅くなるためです。

最小限の反例では、通常の1ビンは存在しない（各ビンには少なくとも2つのアイテムが含まれているため）ので、上記の補題により、FFDビンP1 _、 ...、Pn_はタイプ順に並べられます。

• 0個以上のフォールバック1ビン。
• 次に、0個以上の通常の2ビン。
• 次に、0個以上のフォールバック2ビン。
• 次に、0個以上の通常の3ビン。
• 次に、0個以上のフォールバック3ビン。
• 等々。

上限$\displaystyle r_{n}\leq 1.22$^{[ 1 ]}は、最小限の (122/100) 反例を仮定することで証明されます。各アイテムには、重みられます。重みは、各 FFD ビン内の合計重量が少なくともx、ほぼすべての最適ビン内の合計重量が最大でx(あらかじめ決められたx) となるように決定されます。これは、FFD ビンの数が最適ビンの数以下であることを意味し、反例であるという仮定と矛盾します。

上記の補題から、次のことがわかる。

• 最小のアイテムのサイズはs > p - q = 22 を満たすので、s = 22 + Dとなり、D > 0 となる。
• 最適なビンには最大で4つのアイテムが含まれ（floor(100/22)）、FFDビンには最大で5つのアイテムが含まれます（floor(122/22)）。
• 各アイテムのサイズは最大でq -2 s = 56-2 Dです。
• 各 FFD ビンの合計はp - s = 100 - Dより大きい。
• 1ビンは存在しません。なぜなら、1ビンでは、通常のアイテムのサイズは少なくともp /2=61でなければなりませんが、ここではすべてのアイテムのサイズが56未満だからです。

D > 4の場合、各アイテムのサイズは 26 より大きいので、各最適ビン (容量 100) には最大 3 つのアイテムしか含まれません。各アイテムは 56-2 Dより小さく、各 FFD ビンの合計は 100- Dより大きいので、各 FFD ビンには少なくとも 3 つのアイテムが含まれていなければなりません。したがって、FFD ビンは最大n個しか存在せず、矛盾が生じます。そこで、以降はD ≤ 4 と仮定します。アイテムには、次のようにタイプと重みが割り当てられます。

• 最後の2つのビンを除く各通常の2ビン内の2つのアイテムは、それぞれ(100- D )/2より大きいサイズを持ちます。このようなアイテムはすべてタイプX2_と呼ばれ、(100- D )/2の重量が割り当てられます。最後の2つの通常のビンは特別なケースです。その中の2つのアイテムの両方のサイズが(100- D )/2より大きい場合、それらもタイプX2_になります。そうでない場合は、タイプZと呼ばれ、その重量はサイズに等しくなります。
• 各フォールバック2ビン内の2つの通常アイテムの合計サイズは2*122/3より大きく、タイプY2_と呼ばれ、その重量はサイズからDを引いた値に等しくなります。
• 通常の3ビン内の3つのアイテムのうち、最後のビンを除くすべてのアイテムは、それぞれ(100- D )/3より大きいサイズを持ちます。このようなアイテムはすべてタイプX3_と呼ばれ、(100- D )/3の重量が割り当てられます。最後の3ビンは特別なケースです。ビン内のすべてのアイテムのサイズが(100- D )/3より大きい場合、それらもタイプX3_となります。そうでない場合は、タイプZと呼ばれ、重量はサイズに等しくなります。
• 各フォールバック3ビン内の3つの通常アイテムの合計サイズは3*122/4より大きく、タイプY3_と呼ばれ、その重量はサイズからDを引いた値に等しくなります。
• 通常の4ビン内の4つのアイテムのうち、最後のビンを除くすべてのアイテムは、それぞれ(100- D )/4より大きいサイズを持ちます。このようなアイテムはすべてタイプX4_と呼ばれ、(100- D )/4の重量が割り当てられます。最後の4ビンは特別なケースです。ビン内のすべてのアイテムのサイズが(100- D )/4より大きい場合、それらもタイプX4_となります。そうでない場合は、タイプZと呼ばれ、重量はサイズに等しくなります。
• 残りの項目（フォールバック2ビンおよび3ビンのすべてのフォールバック項目、すべてのフォールバック4ビン、およびその他のすべての5項目ビンを含む）はすべてタイプX ₅と呼ばれ、その重みは22（D ≤ 12/5の場合）または（100- D）/4（それ以外の場合）に等しくなります。しきい値12/5は、重みが常に最大22+ Dになるように計算されており、重みは常にサイズよりも小さくなります。

各アイテムの重量は最大でそのサイズであることに注意してください（重量はサイズを「切り捨てた」ものと考えることができます）。それでも、すべてのFFDビン内のアイテムの総重量は少なくとも100- Dです。

• 通常の2ビン、通常の3ビン、通常の4ビンの場合：
  • 最後以外のものについては、これは即時です。
  • 最後のそのようなビンには、重量がサイズに等しいZタイプのアイテムのみが含まれているため、これらのビンの総重量は総サイズに等しく、100- Dを超えます。
• フォールバック2ビンには、合計重量が2*122/3-2 Dより大きいタイプY ₂アイテムが2つと、重量が22以上（D ≤ 12/5の場合）または（100- D ）/4以上（それ以外の場合）のタイプX _{5アイテムが少なくとも1つ含まれています。どちらの場合も、合計重量は100-} Dより大きくなります。
• フォールバック 3 ビンには、合計重量が 3*122/4-3 Dより大きいタイプ Y _{3アイテムが 3 つと、重量が 22 以上のタイプ X 5}アイテムが1 つ以上含まれています。したがって、合計重量は 3*122/4+22-3 D = 113.5-3 D ≥ 105.5- D > 100- Dより大きくなります。これはD≤ 4であるためです。
• 5 個のアイテムが入った箱には、少なくとも 22+ Dのサイズで、少なくとも 22 の重量のアイテムが 5 つ入っているため、それらの合計重量は明らかに 100- Dを超えています。

最も最適な容器内のアイテムの総重量は最大で100- Dです。

• これは、タイプ-Y ₂アイテムまたはタイプ-Y ₃アイテムを含む任意の最適ビンについて明らかです。なぜなら、それらの重量はサイズからDを引いた値であり、他のアイテムの重量は最大でもそのサイズであり、最適ビンの合計サイズは最大で 100 だからです。
• タイプ-X ₂、タイプ-X ₃、タイプ-X ₄、タイプ-X ₅のアイテムのみを含む最適なビンについては、すべての可能な構成 (サイズ 100 の最適なビンに収まるすべての組み合わせ) をチェックし、各構成での総重量が最大 100- Dであることを検証できます。
• タイプZのアイテムを含む最適なビンは、合計重量が100- Dを超える場合があります。合計重量は最大でも100なので、そのようなビンごとに最大Dの「超過重量」が発生します。ただし、タイプZのアイテムの数は限られています。
  • D > 12/5 の場合、タイプ Z アイテムは最大 5 つになります (最後の通常の 2 ビンに 2 つ、最後の通常の 3 ビンに 3 つ。最後の通常の 4 ビンのアイテムはすべてタイプ X ₄です)。したがって、超過重量は最大 5 Dです。FFD と最適なビンの合計重量を比較すると、s < 5 D ≤ 20 < 22 となり、矛盾が生じます。
  • そうでなければ、タイプZのアイテムは最大で9個（2+3+4）になります。したがって、超過重量は最大で9Dです。FFDと最適ビンの合計重量を比較すると、s < 9D ≤ 108/5 < 22となり、矛盾が生じます。

上限$\displaystyle r_{n}\leq 13/11\approx 1.182$^{[ 3 ]は}、 d<最小の((120-3d)/100)反例を仮定し、矛盾を導き出すことによって証明される。

以下に例を示します。^{[ 5 ]：例5.2} 4人のエージェントがいて、2種類の評価を持っているとします。

どちらのタイプも、家事を合計価値75の4つの部分に分割できます。タイプA：

• 51、12、12
• 27.5、27.5、10、10
• 27.5、27.5、10、10
• 25、10、10、10、10、10

タイプB：

• 51、24
• 27.5、27.5、20
• 27.5、27.5、20
• 8.33 {9回}

4 つのエージェントすべてが同じタイプの場合、閾値 75 の FFD は 4 つの最適なビンを埋めます。しかし、タイプ B のエージェントが 1 つあり、他のエージェントがタイプ A であるとします。すると、最初のラウンドでは、タイプ B のエージェントがバンドル 51、24 を取得します (他のエージェントは、値 51、25 の合計が 75 を超えるため、これを取得できません)。次のラウンドでは、タイプ A のエージェントに対して次のバンドルが埋められます。

• 27.5、27.5、12 [合計は67です。これ以上10を入れる余地はありません]
• 27.5、27.5、12 [合計は67です。これ以上10を入れる余地はありません]
• 10、10、10、10、10、10、10 [合計は70です。これ以上10を入れる余地はありません]

そのため、残りの2つの仕事は未割り当てのままです。

より高度な閾値計算を用いることで、最適値が既知の場合は各エージェントに最大で最適値の 11/9≈1.22 を保証でき、最適値が未知の場合は最大で最適値の 5/4≈1.25 を保証することができる (多項式時間アルゴリズムを使用)。^{[ 5 ]}

より詳細な議論を用いることで、各エージェントに同じ比率のMultiFitを保証することが可能です。^{[ 9 ]}