ファーストフィットビンパッキング

フリー百科事典『ウィキペディア』より

ファーストフィット（FF）は、ビンパッキングのためのオンラインアルゴリズムです。入力は、異なるサイズのアイテムのリストです。出力はパッキングです。パッキングとは、アイテムを固定容量のビンに分割することです。各ビンのアイテムのサイズの合計は、最大で容量になります。理想的には、ビンの数はできるだけ少なくしたいのですが、ビンの数を最小化することはNP困難です。ファーストフィットアルゴリズムは、以下のヒューリスティックを使用します。

最初は空である、開いているビンのリストを保持します。
アイテムが到着したら、そのアイテムが収まる最初のビンがあればそれを見つけます。
- そのようなビンが見つかった場合、新しいアイテムはその中に配置されます。
- それ以外の場合は、新しいビンが開かれ、その中に新しいアイテムが配置されます。

近似比

FF(L) は First-Fit で使用されるビンの数、OPT(L) はリスト L で可能な最適なビンの数を表します。FF(L) の分析はいくつかのステップで実行されました。

FFの上限値は1971年にUllman ^[¹^]によって初めて証明された。 $FF(L)\leq 1.7\mathrm {OPT} +3$
1972年にこの上限はGarey、Graham、Ullman、^[²^] Johnson、Demersによって改良されました。^[³^] $FF(L)\leq 1.7\mathrm {OPT} +2$
^{1976年にGarey、Graham、Johnson、Yao、Chi-Chih [ 4 ]}によって改良されとなり、これはとの整数性によりと等価となった。 $FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil$ $FF(L)\leq 1.7\mathrm {OPT} +0.9$ $FF(L)$ $\mathrm {OPT}$
2010年にXiaとTan ^{[ 5 ]}が行った次の改良により、その上限はまで引き下げられました。 $FF(L)\leq 1.7\mathrm {OPT} +0.7$
最終的に、2013年に、この境界はDósaとSgallによってまで改良されました。^[⁶^]彼らはまた、この境界に一致する入力リストの例も提示しています。 $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ $L$ $FF(L)$

以下に証明の考え方を説明します。

漸近比は最大2

漸近比が最大で2であることの証明を示します。FFビンの合計が1/2未満の場合、残りのすべてのアイテムのサイズは1/2以上であるため、それに続くすべてのビンの合計は1/2以上になります。したがって、最大で1つを除くすべてのFFビンの合計は少なくとも1/2です。すべての最適なビンの合計は最大で1であるため、すべてのサイズの合計は最大でOPTです。したがって、FFビンの数は最大で1+OPT/(1/2) = 2*OPT+1です。

漸近比は最大1.75

まず、すべてのアイテムのサイズが最大で1/2である特殊なケースを考えてみましょう。合計が2/3未満のFFビンがある場合、残りのすべてのアイテムのサイズは1/3を超えます。サイズが最大で1/2であるため、後続のビン（最後のビンを除く）には少なくとも2つのアイテムがあり、合計は2/3を超えます。したがって、最大で1つのFFビンを除くすべてのFFビンの合計は少なくとも2/3であり、FFビンの数は最大で2+OPT/(2/3) = 3/2*OPT+1となります。

「問題のある」アイテムとは、サイズが1/2より大きいアイテムです。そこで、分析を改善するために、1/2より大きいすべてのアイテムにRのボーナスを与えましょう。アイテムの重さは、そのサイズにボーナスを加えたものと定義します。アイテムセットの重さは、その中の各アイテムの重さの合計と定義します。

ここで、1つのアイテム（最大1つを除く）を含む各FFビンの重みは少なくとも1/2+Rであり、2つ以上のアイテム（最大1つを除く）を含む各FFビンの重みは2/3です。R=1/6とすると、すべてのFFビンの重みは少なくとも2/3になります。

一方、最適パッキングにおける各ビンの重量は最大で1+R = 7/6です。これは、各ビンには1/2より大きいアイテムが最大で1つしか含まれていないためです。したがって、すべてのアイテムの合計重量は最大で7/6*OPTとなり、FFビンの数は最大で2+(7/6*OPT/(2/3)) = 7/4*OPT+2となります。

漸近比は最大1.7

以下の証明は^{[ 6 ]}^{から引用したものです。 :sec.1.2}入力アイテムの重みをアイテムサイズ×以下のように計算されるボーナスとして定義します。

$bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}$

$重み(x):=x+ボーナス(x)$ 。

漸近近似比は、次の 2 つの主張から導かれます。

最適な梱包では、各ビンの重量は最大で 17/12 になります。
First-Fit パッキングでは、各ビンの平均重量は少なくとも 5/6 = 10/12 になります。

したがって、漸近的には、FF パッキング内のビンの数は最大で 17/10 * OPT である必要があります。

主張1については、和が1以下の任意の集合Bに対して、bonus( B )が5/12以下であることを証明すれば十分である。実際、

Bに 1/2 より大きい項目がない場合、1/6 より大きい項目は最大で 5 つあり、それぞれのボーナスは最大で 1/12 です。
Bに 1/2 より大きいアイテムがあり、[1/3,1/2] にアイテムがない場合、(1/6,1/3) には最大で 2 つのアイテムを配置できる余地があり、そのボーナスの合計は最大で (1/2 / 2 - 1/6) = 1/12 となるため、合計ボーナスは 4/12+1/12=5/12 となります。
B に1/2 より大きいアイテムと [1/3,1/2] 内のアイテムがある場合、1/6 より大きいサイズのアイテムを配置する余地はもうないため、合計ボーナスは再び 4/12+1/12 = 5/12 になります。

したがって、 Bの重みは最大で 1+5/12 = 17/12 になります。

クレーム 2については、まず1 つのアイテムを含むFF ビンBを検討します。

sum( B )<1/2 の場合、FF の仕組み上、Bの後に処理されるすべての項目は 1/2 より大きくなければなりません（そうでなければ、それらはBに挿入されます）。したがって、sum<1/2 となる FF ビンは最大で 1 つ存在します。
次に、合計( B )>1/2となる単一のアイテムを含む他のすべてのビンBについて考えてみましょう。これらのビンすべてにおいて、重み( B )>1/2+1/3 = 5/6となります。

ここで、 2 つ以上のアイテムを含むFF ビンBを検討します。

sum( B )<2/3 の場合、FF の仕組み上、Bの後に処理されるすべてのアイテムは 1/3 より大きくなければなりません（そうでなければ、それらはBに挿入されます）。したがって、2 個以上のアイテムを含む後続のビンはすべて 2/3 より大きくなります。したがって、2 個以上のアイテムを含み、かつ sum<2/3 となる FF ビンは最大で 1 つしかありません。
次に、2つ以上のアイテムを持ち、合計が2/3を超える他のすべてのビンについて考えます。開封順に、それらをB[1]、B[2]、...B[k]と表記します。1 ,..., k内の各iについて、B[i]の合計とB[i+1]のボーナスの合計が少なくとも5/6であることを証明します。つまり、sum(B[i])+bonus(B[i+1]) ≥ 5/6です。実際、sum(B[i]) ≥ 5/6であれば、不等式は自明です。それ以外の場合は、sum(B[i]) := 1 - xとします。sum (B[i]) が2/3から5/6の間であるため、 xは1/6から2/6の間であることに注意してください。 B[i+1]はB[i]の後に開かれるため、B[i+1]にはB[i]に収まらない少なくとも2つの項目（例えばc 1 とc 2）が含まれます。つまり、c1,c2 > 1-sum(B[i]) = x > 1/6となります。すると、c1とc2のそれぞれのボーナスは少なくともx/2 - 1/12となります。したがって、B[i+1]のボーナスは少なくともx-1/6となり、sum(B[i]) + bonus(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6となります。
上記の不等式を連続するペアに適用すると、sum(B[1]) + bonus(B[2]) + sum(B[2]) + bonus(B[3]) + ... + sum(B[k-1]) + bonus(B[k]) ≥ 5/6*(k-1)となります。

したがって、すべての FF ビンの合計重みは少なくとも 5/6*(FF - 3) になります (ここで、合計が 1/2 未満の単一の 1 項目ビン、合計が 2/3 未満の単一の 2 項目ビン、および合計が 2/3 以上の 2 項目ビンから k-1 を減算します)。

全体として、17/12*OPT ≥ 5/6*(FF-3) となり、FF ≤ 17/10*OPT+3 となります。

DósaとSgall ^{[ 6 ]}は、3を取り除いたより厳密な解析を提示し、FF≤17/10*OPTを得ています。

下限

1.7OPTの性能限界が厳しいケースがあります。以下の例は^{[ 7 ]}^{[ 8 ]}に基づいています。ビンの容量は101で、

順序は、6 (x7)、10 (x7)、16 (x3)、34 (x10)、51 (x10) です。
最適なパッキングには10個のビンが含まれます：[51+34+16] (x3)、[51+34+10+6] (x7)。すべてのビンの合計は101です。
ファーストフィットパッキングには17個のビンが含まれています: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5)、[51] (x10)。
- ビンの合計は、92、68、68 (x5)、51 (x10) です。
- 報酬（101 に正規化）は、0、0、16.8（x5）、33.7（x10）です。
- 合計重み（101に正規化）は92、68、84.8（5倍）、84.7（10倍）です。ほぼすべての重みが101*5/6=84.1に近いことがわかります。

分割可能なアイテムサイズのパフォーマンス

ビンパッキングの重要な特殊ケースとして、アイテムサイズが割り切れるシーケンス（因数分解とも呼ばれる）を形成するケースがあります。割り切れるアイテムサイズの特殊ケースは、コンピュータシステムにおけるメモリ割り当てにおいて発生します。この場合、アイテムサイズはすべて2の累乗です。アイテムサイズが割り切れ、さらに最大のアイテムサイズがビンサイズを割り切る場合、FFは常に最適なパッキングを見つけます。^{[ 9 ]}^：Thm.3

改良されたファーストフィット

Refined-First-Fit（RFF）は、ビンパッキングのための別のオンラインアルゴリズムであり、以前に開発されたFFアルゴリズムを改良したものです。Andrew Chi-Chih Yaoによって発表されました。^[¹⁰^]

アルゴリズム

アイテムは、サイズに応じて 4 つのクラスに分類されます (ビンの容量は 1 です)。

$A$ -ピース-サイズインチ。 $(1/2,1]$
$B_{1}$ -ピース-サイズインチ。 $(2/5,1/2]$
$B_{2}$ -ピース-サイズインチ。 $(1/3,2/5]$
$X$ -ピース-サイズインチ。 $(0,1/3]$

同様に、ビンは 1、2、3、4 の 4 つのクラスに分類されます。

を固定整数とする。次のアイテムは、以下のビンに割り当てられる。 $m\in \{6,7,8,9\}$ $i\in L$

クラス1、が -ピースの場合、 $i$ $A$
クラス2、が -ピースの場合、 $i$ $B_{1}$
クラス 3、が-ピースであるが、任意の整数に対して、これまでに見た番目の -ピースではない場合。 $i$ $B_{2}$ $(mk)$ $B_{2}$ $k\geq 1$
クラス1、がこれまでに見た番目のピースである場合、 $i$ $(mk)$ $B_{2}$
クラス 4、が- ピースの場合。 $i$ $X$

アイテムのクラスが選択されると、ファーストフィットビンパッキングを使用してそのクラスのビン内に配置されます。

RFF は、現在のアイテムが (別のクラスの) 開いているビン内に収まるにもかかわらず、新しいビンを開く可能性があるため、Any-Fit アルゴリズムではないことに注意してください。

近似比

RFFはの近似値保証を持つ。に対してとなるリストの族が存在する。^[¹⁰^] $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ $L_{k}$ $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ $\mathrm {OPT} (L)=6k+1$

参照

First-Fit-Decreasing（FFD）は、First-Fitのオフライン版です。すべての入力項目を受け取り、サイズが降順になるように並べ替え、First-Fitを呼び出します。漸近近似比は1.7ではなく約1.222と、First-Fitよりもはるかに優れています。

実装

Python: prtpyパッケージにはfirst-fit の実装が含まれています。

参考文献

^ Ullman, JD (1971). 「メモリ割り当てアルゴリズムの性能」.プリンストン大学技術レポート100 .
^ Garey, M. R; Graham, R. L; Ullman, JD (1972). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACMコンピューティング理論シンポジウム議事録 - STOC '72 . pp. 143– 150. doi : 10.1145/800152.804907 . S2CID 26654056 .
^ David S. Johnson、Alan J. Demers、Jeffrey D. Ullman、MR Garey、Ronald L. Graham.「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 SICOMP、第3巻、第4号、1974年。
^ Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). 「一般化ビンパッキングとしてのリソース制約スケジューリング」 . Journal of Combinatorial Theory, Series A. 21 ( 3): 257– 298. doi : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165 .
^ Xia, Binzhou; Tan, Zhiyi (2010年8月). 「ビンパッキング問題におけるFirst Fitアルゴリズムのより厳しい境界」 .離散応用数学. 158 (15): 1668– 1675. doi : 10.1016/j.dam.2010.05.026 .
^ ^a ^b ^c ドーサ、ジェルジュ;スガール、ジリ (2013)。「First Fit ビンのパッキング: 綿密な分析」。コンピュータサイエンスの理論的側面に関する第 30 回国際シンポジウム (STACS 2013)。２０． Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538– 549. doi : 10.4230/LIPIcs.STACS.2013.538。
^ Garey, MR; Graham, RL; Ullman, JD (1972-05-01). 「メモリ割り当てアルゴリズムの最悪ケース解析」 .第4回ACM計算理論シンポジウム議事録 - STOC '72 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 143– 150. doi : 10.1145/800152.804907 . ISBN 978-1-4503-7457-6. S2CID 26654056 .
^ Johnson, DS; Demers, A.; Ullman, JD; Garey, MR; Graham, RL (1974年12月). 「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 . SIAM Journal on Computing . 3 (4): 299– 325. doi : 10.1137/0203025 . ISSN 0097-5397 .
^ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). 「分割可能なアイテムサイズによるビンパッキング」 . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .
^ ^a ^b Yao, Andrew Chi-Chih (1980年4月). 「ビンパッキングのための新しいアルゴリズム」 . Journal of the ACM . 27 (2): 207– 227. doi : 10.1145/322186.322187 . S2CID 7903339 .

ファーストフィット（FF）は、ビンパッキングのためのオンラインアルゴリズムです。入力は、異なるサイズのアイテムのリストです。出力はパッキングです。パッキングとは、アイテムを固定容量のビンに分割することです。各ビンのアイテムのサイズの合計は、最大で容量になります。理想的には、ビンの数はできるだけ少なくしたいのですが、ビンの数を最小化することはNP困難です。ファーストフィットアルゴリズムは、以下のヒューリスティックを使用します。

最初は空である、開いているビンのリストを保持します。
アイテムが到着したら、そのアイテムが収まる最初のビンがあればそれを見つけます。
- そのようなビンが見つかった場合、新しいアイテムはその中に配置されます。
- それ以外の場合は、新しいビンが開かれ、その中に新しいアイテムが配置されます。

近似比

FF(L) は First-Fit で使用されるビンの数、OPT(L) はリスト L で可能な最適なビンの数を表します。FF(L) の分析はいくつかのステップで実行されました。

FFの上限値の最初の値は1971年にUllman ^[1]によって証明された。 $FF(L)\leq 1.7\mathrm {OPT} +3$
1972年に、この上限はGarey、Graham、Ullman、^[2] Johnson、Demersによって改良されました。^[3] $FF(L)\leq 1.7\mathrm {OPT} +2$
^{1976年にGarey、Graham、Johnson、Yao、Chi-Chih [4]}によってに改良され、との整数性によりと等価になった。 $FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil$ $FF(L)\leq 1.7\mathrm {OPT} +0.9$ $FF(L)$ $\mathrm {OPT}$
^{2010年にXiaとTan [5]}が行った次の改良により、上限はまで引き下げられました。 $FF(L)\leq 1.7\mathrm {OPT} +0.7$
最終的に、2013年に、この境界はDósaとSgallによってまで改良されました。^[6]彼らはまた、この境界に一致するという入力リストの例を示すこともしています。 $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ $L$ $FF(L)$

以下に証明の考え方を説明します。

漸近比は最大2

漸近比が最大で2であることの証明を示します。FFビンの合計が1/2未満の場合、残りのすべてのアイテムのサイズは1/2以上であるため、それに続くすべてのビンの合計は1/2以上になります。したがって、最大で1つを除くすべてのFFビンの合計は少なくとも1/2です。すべての最適なビンの合計は最大で1であるため、すべてのサイズの合計は最大でOPTです。したがって、FFビンの数は最大で1+OPT/(1/2) = 2*OPT+1です。

漸近比は最大1.75

まず、すべてのアイテムのサイズが最大で1/2である特殊なケースを考えてみましょう。合計が2/3未満のFFビンがある場合、残りのすべてのアイテムのサイズは1/3を超えます。サイズが最大で1/2であるため、後続のビン（最後のビンを除く）には少なくとも2つのアイテムがあり、合計は2/3を超えます。したがって、最大で1つのFFビンを除くすべてのFFビンの合計は少なくとも2/3であり、FFビンの数は最大で2+OPT/(2/3) = 3/2*OPT+1となります。

「問題のある」アイテムとは、サイズが1/2より大きいアイテムです。そこで、分析を改善するために、1/2より大きいすべてのアイテムにRのボーナスを与えましょう。アイテムの重さは、そのサイズにボーナスを加えたものと定義します。アイテムセットの重さは、その中の各アイテムの重さの合計と定義します。

ここで、1つのアイテム（最大1つを除く）を含む各FFビンの重みは少なくとも1/2+Rであり、2つ以上のアイテム（最大1つを除く）を含む各FFビンの重みは2/3です。R=1/6とすると、すべてのFFビンの重みは少なくとも2/3になります。

一方、最適パッキングにおける各ビンの重量は最大で1+R = 7/6です。これは、各ビンには1/2より大きいアイテムが最大で1つしか含まれていないためです。したがって、すべてのアイテムの合計重量は最大で7/6*OPTとなり、FFビンの数は最大で2+(7/6*OPT/(2/3)) = 7/4*OPT+2となります。

漸近比は最大1.7

以下の証明は^{[6]から引用したものです。}^{: sec.1.2}入力アイテムの重みをアイテムサイズ×以下のように計算されるボーナスとして定義します。

$bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}$

$重み(x):=x+ボーナス(x)$ 。

漸近近似比は、次の 2 つの主張から導かれます。

最適な梱包では、各ビンの重量は最大で 17/12 になります。
First-Fit パッキングでは、各ビンの平均重量は少なくとも 5/6 = 10/12 になります。

したがって、漸近的には、FF パッキング内のビンの数は最大で 17/10 * OPT である必要があります。

主張1については、和が1以下の任意の集合Bに対して、bonus( B )が5/12以下であることを証明すれば十分である。実際、

Bに 1/2 より大きい項目がない場合、1/6 より大きい項目は最大で 5 つあり、それぞれのボーナスは最大で 1/12 です。
Bに 1/2 より大きいアイテムがあり、[1/3,1/2] にアイテムがない場合、(1/6,1/3) には最大で 2 つのアイテムを配置できる余地があり、そのボーナスの合計は最大で (1/2 / 2 - 1/6) = 1/12 となるため、合計ボーナスは 4/12+1/12=5/12 となります。
B に1/2 より大きいアイテムと [1/3,1/2] 内のアイテムがある場合、1/6 より大きいサイズのアイテムを配置する余地はもうないため、合計ボーナスは再び 4/12+1/12 = 5/12 になります。

したがって、 Bの重みは最大で 1+5/12 = 17/12 になります。

クレーム 2については、まず1 つのアイテムを含むFF ビンBを検討します。

sum( B )<1/2 の場合、FF の仕組み上、Bの後に処理されるすべての項目は 1/2 より大きくなければなりません（そうでなければ、それらはBに挿入されます）。したがって、sum<1/2 となる FF ビンは最大で 1 つ存在します。
次に、合計( B )>1/2となる単一のアイテムを含む他のすべてのビンBについて考えてみましょう。これらのビンすべてにおいて、重み( B )>1/2+1/3 = 5/6となります。

ここで、 2 つ以上のアイテムを含むFF ビンBを検討します。

sum( B )<2/3 の場合、FF の仕組み上、Bの後に処理されるすべてのアイテムは 1/3 より大きくなければなりません（そうでなければ、それらはBに挿入されます）。したがって、2 個以上のアイテムを含む後続のビンはすべて 2/3 より大きくなります。したがって、2 個以上のアイテムを含み、かつ sum<2/3 となる FF ビンは最大で 1 つしかありません。
次に、2つ以上のアイテムを持ち、合計が2/3を超える他のすべてのビンについて考えます。開封順に、それらをB[1]、B[2]、...B[k]と表記します。1 ,..., k内の各iについて、B[i]の合計とB[i+1]のボーナスの合計が少なくとも5/6であることを証明します。つまり、sum(B[i])+bonus(B[i+1]) ≥ 5/6です。実際、sum(B[i]) ≥ 5/6であれば、不等式は自明です。それ以外の場合は、sum(B[i]) := 1 - xとします。sum (B[i]) が2/3から5/6の間であるため、 xは1/6から2/6の間であることに注意してください。 B[i+1]はB[i]の後に開かれるため、B[i+1]にはB[i]に収まらない少なくとも2つの項目（例えばc 1 とc 2）が含まれます。つまり、c1,c2 > 1-sum(B[i]) = x > 1/6となります。すると、c1とc2のそれぞれのボーナスは少なくともx/2 - 1/12となります。したがって、B[i+1]のボーナスは少なくともx-1/6となり、sum(B[i]) + bonus(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6となります。
上記の不等式を連続するペアに適用すると、sum(B[1]) + bonus(B[2]) + sum(B[2]) + bonus(B[3]) + ... + sum(B[k-1]) + bonus(B[k]) ≥ 5/6*(k-1)となります。

したがって、すべての FF ビンの合計重みは少なくとも 5/6*(FF - 3) になります (ここで、合計が 1/2 未満の単一の 1 項目ビン、合計が 2/3 未満の単一の 2 項目ビン、および合計が 2/3 以上の 2 項目ビンから k-1 を減算します)。

全体として、17/12*OPT ≥ 5/6*(FF-3) となり、FF ≤ 17/10*OPT+3 となります。

DósaとSgall ^[6]は、3を取り除いたより厳密な分析を提示し、FF≤17/10*OPTを得ています。

下限

1.7OPTの性能限界が厳しいケースがあります。以下の例は^[7]^[8]に基づいています。ビンの容量は101で、

順序は、6 (x7)、10 (x7)、16 (x3)、34 (x10)、51 (x10) です。
最適なパッキングには10個のビンが含まれます：[51+34+16] (x3)、[51+34+10+6] (x7)。すべてのビンの合計は101です。
ファーストフィットパッキングには17個のビンが含まれています: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5)、[51] (x10)。
- ビンの合計は、92、68、68 (x5)、51 (x10) です。
- 報酬（101 に正規化）は、0、0、16.8（x5）、33.7（x10）です。
- 合計重み（101に正規化）は92、68、84.8（5倍）、84.7（10倍）です。ほぼすべての重みが101*5/6=84.1に近いことがわかります。

分割可能なアイテムサイズのパフォーマンス

ビンパッキングの重要な特殊なケースとして、アイテムサイズが割り切れるシーケンス（因数分解とも呼ばれる）を形成するケースがあります。割り切れるアイテムサイズの特殊なケースは、コンピュータシステムにおけるメモリ割り当てにおいて発生します。この場合、アイテムサイズはすべて2の累乗です。アイテムサイズが割り切れ、さらに最大のアイテムサイズがビンサイズを割り切る場合、FFは常に最適なパッキングを見つけます。^[9]^{: Thm.3}

改良されたファーストフィット

Refined-First-Fit（RFF）は、ビンパッキングのための別のオンラインアルゴリズムであり、以前に開発されたFFアルゴリズムを改良したものです。Andrew Chi-Chih Yaoによって発表されました。^[10]

アルゴリズム

アイテムは、サイズに応じて 4 つのクラスに分類されます (ビンの容量は 1 です)。

$A$ -ピース-サイズインチ。 $(1/2,1]$
$B_{1}$ -ピース-サイズインチ。 $(2/5,1/2]$
$B_{2}$ -ピース-サイズインチ。 $(1/3,2/5]$
$X$ -ピース-サイズインチ。 $(0,1/3]$

同様に、ビンは 1、2、3、4 の 4 つのクラスに分類されます。

を固定整数とする。次のアイテムは、以下のビンに割り当てられる。 $m\in \{6,7,8,9\}$ $i\in L$

クラス1、が -ピースの場合、 $i$ $A$
クラス2、が -ピースの場合、 $i$ $B_{1}$
クラス 3、が-ピースであるが、任意の整数に対して、これまでに見た番目の -ピースではない場合。 $i$ $B_{2}$ $(mk)$ $B_{2}$ $k\geq 1$
クラス1、がこれまでに見た番目のピースである場合、 $i$ $(mk)$ $B_{2}$
クラス 4、が- ピースの場合。 $i$ $X$

アイテムのクラスが選択されると、ファーストフィットビンパッキングを使用してそのクラスのビン内に配置されます。

RFF は、現在のアイテムが (別のクラスの) 開いているビン内に収まるにもかかわらず、新しいビンを開く可能性があるため、Any-Fit アルゴリズムではないことに注意してください。

近似比

RFFはの近似値保証を持つ。に対してとなるリストの族が存在する。^[10] $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ $L_{k}$ $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ $\mathrm {OPT} (L)=6k+1$

参照

First-Fit-Decreasing（FFD）は、First-Fitのオフライン版です。すべての入力項目を受け取り、サイズが降順になるように並べ替え、First-Fitを呼び出します。漸近近似比は1.7ではなく約1.222と、First-Fitよりもはるかに優れています。

実装

Python: prtpy パッケージには first-fit の実装が含まれています。

参考文献

^ Ullman, JD (1971). 「メモリ割り当てアルゴリズムの性能」.プリンストン大学技術レポート100 .
^ Garey, M. R; Graham, R. L; Ullman, JD (1972). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACMコンピューティング理論シンポジウム議事録 - STOC '72 . pp. 143– 150. doi :10.1145/800152.804907. S2CID 26654056.
^ David S. Johnson、Alan J. Demers、Jeffrey D. Ullman、M.R. Garey、Ronald L. Graham.「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」SICOMP、第3巻、第4号、1974年。
^ Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). 「一般化ビンパッキングとしてのリソース制約スケジューリング」. Journal of Combinatorial Theory, Series A. 21 ( 3): 257– 298. doi : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165.
^ Xia, Binzhou; Tan, Zhiyi (2010年8月). 「ビンパッキング問題におけるFirst Fitアルゴリズムのより厳しい境界」.離散応用数学. 158 (15): 1668– 1675. doi : 10.1016/j.dam.2010.05.026 .
^ abc ドーサ、ジェルジュ;スガール、ジリ (2013)。「First Fit ビンのパッキング: 綿密な分析」。コンピュータサイエンスの理論的側面に関する第 30 回国際シンポジウム (STACS 2013)。２０． Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538– 549. doi : 10.4230/LIPIcs.STACS.2013.538。
^ Garey, MR; Graham, RL; Ullman, JD (1972-05-01). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACM計算理論シンポジウム議事録 - STOC '72 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 143– 150. doi :10.1145/800152.804907. ISBN 978-1-4503-7457-6. S2CID 26654056。
^ Johnson, DS; Demers, A.; Ullman, JD; Garey, MR; Graham, RL (1974年12月). 「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 . SIAM Journal on Computing . 3 (4): 299– 325. doi :10.1137/0203025. ISSN 0097-5397.
^ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). 「分割可能なアイテムサイズによるビンパッキング」 . Journal of Complexity . 3 (4): 406– 428. doi :10.1016/0885-064X(87)90009-4. ISSN 0885-064X.
^ ab Yao, Andrew Chi-Chih (1980年4月). 「ビンパッキングのための新しいアルゴリズム」. Journal of the ACM . 27 (2): 207– 227. doi : 10.1145/322186.322187 . S2CID 7903339.

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

[Ullman713-1] Ullman, JD (1971). 「メモリ割り当てアルゴリズムの性能」.プリンストン大学技術レポート100 .

[GareyGU723-2] Garey, M. R; Graham, R. L; Ullman, JD (1972). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACMコンピューティング理論シンポジウム議事録 - STOC '72 . pp. 143– 150. doi : 10.1145/800152.804907 . S2CID 26654056 .

[3] David S. Johnson、Alan J. Demers、Jeffrey D. Ullman、MR Garey、Ronald L. Graham.「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 SICOMP、第3巻、第4号、1974年。

[GareyGJY3-4] Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). 「一般化ビンパッキングとしてのリソース制約スケジューリング」 . Journal of Combinatorial Theory, Series A. 21 ( 3): 257– 298. doi : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165 .

[5] Xia, Binzhou; Tan, Zhiyi (2010年8月). 「ビンパッキング問題におけるFirst Fitアルゴリズムのより厳しい境界」 .離散応用数学. 158 (15): 1668– 1675. doi : 10.1016/j.dam.2010.05.026 .

[DósaSgall2-6] ドーサ、ジェルジュ;スガール、ジリ (2013)。「First Fit ビンのパッキング: 綿密な分析」。コンピュータサイエンスの理論的側面に関する第 30 回国際シンポジウム (STACS 2013)。２０． Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538– 549. doi : 10.4230/LIPIcs.STACS.2013.538。

[7] Garey, MR; Graham, RL; Ullman, JD (1972-05-01). 「メモリ割り当てアルゴリズムの最悪ケース解析」 .第4回ACM計算理論シンポジウム議事録 - STOC '72 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 143– 150. doi : 10.1145/800152.804907 . ISBN 978-1-4503-7457-6. S2CID 26654056 .

[8] Johnson, DS; Demers, A.; Ullman, JD; Garey, MR; Graham, RL (1974年12月). 「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 . SIAM Journal on Computing . 3 (4): 299– 325. doi : 10.1137/0203025 . ISSN 0097-5397 .

[9] Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). 「分割可能なアイテムサイズによるビンパッキング」 . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .

[Yao1980-10] Yao, Andrew Chi-Chih (1980年4月). 「ビンパッキングのための新しいアルゴリズム」 . Journal of the ACM . 27 (2): 207– 227. doi : 10.1145/322186.322187 . S2CID 7903339 .

[Ullman713-1] Ullman, JD (1971). 「メモリ割り当てアルゴリズムの性能」.プリンストン大学技術レポート100 .

[GareyGU723-2] Garey, M. R; Graham, R. L; Ullman, JD (1972). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACMコンピューティング理論シンポジウム議事録 - STOC '72 . pp. 143– 150. doi :10.1145/800152.804907. S2CID 26654056.

[3] David S. Johnson、Alan J. Demers、Jeffrey D. Ullman、M.R. Garey、Ronald L. Graham.「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」SICOMP、第3巻、第4号、1974年。

[GareyGJY3-4] Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). 「一般化ビンパッキングとしてのリソース制約スケジューリング」. Journal of Combinatorial Theory, Series A. 21 ( 3): 257– 298. doi : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165.

[5] Xia, Binzhou; Tan, Zhiyi (2010年8月). 「ビンパッキング問題におけるFirst Fitアルゴリズムのより厳しい境界」.離散応用数学. 158 (15): 1668– 1675. doi : 10.1016/j.dam.2010.05.026 .

[DósaSgall2-6] ドーサ、ジェルジュ;スガール、ジリ (2013)。「First Fit ビンのパッキング: 綿密な分析」。コンピュータサイエンスの理論的側面に関する第 30 回国際シンポジウム (STACS 2013)。２０． Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538– 549. doi : 10.4230/LIPIcs.STACS.2013.538。

[7] Garey, MR; Graham, RL; Ullman, JD (1972-05-01). 「メモリ割り当てアルゴリズムの最悪ケース解析」.第4回ACM計算理論シンポジウム議事録 - STOC '72 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 143– 150. doi :10.1145/800152.804907. ISBN 978-1-4503-7457-6. S2CID 26654056。

[8] Johnson, DS; Demers, A.; Ullman, JD; Garey, MR; Graham, RL (1974年12月). 「単純な1次元パッキングアルゴリズムの最悪ケース性能限界」 . SIAM Journal on Computing . 3 (4): 299– 325. doi :10.1137/0203025. ISSN 0097-5397.

[9] Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). 「分割可能なアイテムサイズによるビンパッキング」 . Journal of Complexity . 3 (4): 406– 428. doi :10.1016/0885-064X(87)90009-4. ISSN 0885-064X.

[Yao1980-10] Yao, Andrew Chi-Chih (1980年4月). 「ビンパッキングのための新しいアルゴリズム」. Journal of the ACM . 27 (2): 207– 227. doi : 10.1145/322186.322187 . S2CID 7903339.

[

[

[

1976年にGarey、Graham、Johnson、Yao、Chi-Chih [ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[