ビンパッキング問題

ビンパッキング問題^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}は最適化問題であり、異なるサイズのアイテムを、それぞれ固定容量の有限個のビンまたはコンテナに、使用するビンの数を最小限に抑える方法で詰め込む必要があります。この問題には、コンテナの充填、重量容量制約のあるトラックへの積載、メディアへのファイルバックアップの作成、ネットワークプレフィックスを複数のサブネットに分割すること^{[ 5 ]} 、 FPGA 半導体チップ設計におけるテクノロジーマッピングなど、多くの応用例があります。

計算上、この問題はNP困難であり、対応する決定問題（指定された数のビンにアイテムが収まるかどうかを判定する問題）はNP完全である。最悪ケースの困難さにもかかわらず、この問題の非常に大きなインスタンスに対する最適な解は、高度なアルゴリズムによって生成できる。さらに、多くの近似アルゴリズムが存在する。たとえば、ファーストフィットアルゴリズムは、各アイテムを最初に収まるビンに配置することで、高速だが多くの場合最適ではない解を提供する。このアルゴリズムはΘ ( n log n )の時間を必要とする。ここでnは梱包するアイテムの数である。アイテムのリストを最初に降順にソートすることで、このアルゴリズムははるかに効率的になる（ファーストフィット降順アルゴリズムと呼ばれることもある）が、それでも最適な解が保証されるわけではなく、リストが長い場合はアルゴリズムの実行時間が長くなる可能性がある。しかし、ファーストフィットが最適な解を生成できるアイテムの順序が少なくとも1つ常に存在することが知られている。^[⁶^]

この問題には、2Dパッキング、線形パッキング、重量によるパッキング、コストによるパッキングなど、多くのバリエーションがあります。ビンパッキング問題は、カッティングストック問題の特殊なケースと見なすこともできます。ビンの数が1つに制限され、各アイテムが体積と価値の両方で特徴付けられる場合、ビンに収まるアイテムの価値を最大化する問題は、ナップサック問題として知られています。

実際に発生するビンパッキングの変形として、ビンに詰め込む際にアイテムがスペースを共有できる場合が挙げられます。具体的には、アイテムのセットを一緒に詰め込んだ場合、個々のアイテムのサイズの合計よりも少ないスペースしか占めない場合があります。この変形は、^仮想マシン( ^{VM )}をサーバーに詰め込む際に、VM 間で共有されるページは一度だけ保存すれば済むため、必要なメモリの総量が減少することから、VM パッキング [ 7 ]と呼ばれています。アイテムが任意の方法でスペースを共有できる場合、ビンパッキングの問題を近似することさえ困難です。しかし、仮想マシンのメモリ共有のように、スペース共有が階層構造になっている場合は、ビンパッキングの問題を効率的に近似することができます。

実務上関心を集めるもう一つのビンパッキング方式は、いわゆるオンラインビンパッキングです。この方式では、異なる容量の品物が順番に到着し、意思決定者は現在確認している品物を選択して梱包するか、そのまま通過させるかを決定しなければなりません。各決定は取り消しできません。一方、オフラインビンパッキングでは、追加の品物が到着した際に、より良い梱包を実現するために品物を並べ替えることができます。もちろん、そのためには並べ替える品物を保管するための追加の保管スペースが必要となります。

正式な声明

『Computers and Intractability』^{[ 8 ]}^{: 226}において、GareyとJohnsonは参照文献[SR1]の下にビンパッキング問題をリストアップしている。彼らはその決定変種を次のように定義している。

インスタンス：有限集合 $I$ アイテムのサイズ $\displaystyle s(i)\in \mathbb {Z} ^{+}}$ 各 $i\in I$ 正の整数ビン容量 $B$ 、そして正の整数 $K$ 。

質問: パーティションはありますか $I$ 互いに素な集合に $I_{1},\dots ,I_{K}$ 各アイテムのサイズの合計が $I_{j}$ は $B$ あるいはそれ以下？

文献では、しばしば代替の表記法が使用されるが、これは等価ではないことに注意する。 $B=1$ そして $s(i)\in \mathbb {Q} \cap (0,1]$ 各 $i\in I$ さらに、研究は主に最適化の変種に関心があり、これは可能な限り最小の値を求めます。 $K$ 解が最適であるのは、 $K$ . $K$ - 一連のアイテムに対する最適解の値 $I$ は、 $\mathrm {OPT} (I)$ または単に $\mathrm {OPT}$ 文脈から項目のセットが明確である場合。

この問題の考えられる整数線形計画法による定式化は以下のとおりです。

どこ $\displaystyle y_j=1}$ bin の場合 $j$ 使用され、 $x_{ij}=1$ アイテムの場合 $i$ ゴミ箱に入れられる $j$ [ ⁹^]

ビンパッキングの硬さ

ビンパッキング問題は強いNP完全問題である。これは、強いNP完全問題である 3分割問題をビンパッキング問題に還元することで証明できる。^{[ 8 ]}

さらに、絶対近似比が以下の値より小さい近似アルゴリズムは存在しない。 $\displaystyle {\tfrac {3}{2}}}$ ない限り ${\mathsf {P}}={\mathsf {NP}}$ これは、分割問題からの還元によって証明できます。[ ^{10 ]すべて}の入力数値の合計が次のようになる分割のインスタンスが与えられた場合、 $2T$ $ビンのサイズがT$ であるビンパッキングのインスタンスを構築します。入力が均等に分割されている場合、最適なパッキングには 2 つのビンが必要です。したがって、近似比が3 / 2より小さいすべてのアルゴリズムは、 3 つのビン未満、つまり 2 つのビンを返す必要があります。対照的に、入力が均等に分割されていない場合、最適なパッキングには少なくとも 3 つのビンが必要です。

一方、ビンパッキングは、ビンの数 $Kが固定されている場合は$ 擬似多項式時間で解くことができ、ビンの容量 $B$ が固定されている場合は多項式時間で解くことができる。^[⁸^]

ビンパッキングのための近似アルゴリズム

近似アルゴリズムの性能を測定するために、文献では2つの近似比が考慮されている。与えられた項目のリストに対して、 $L$ 番号 $A(L)$ アルゴリズムが使用されるビンの数を表します $A$ リストに適用されます $L$ 、その間 $\mathrm {OPT} (L)$ このリストの最適値を示します。絶対最悪の場合のパフォーマンス比 $R_{A}$ アルゴリズムの場合 $A$ は次のように定義される。

R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.

一方、漸近的な最悪ケース比率は $R_{A}^{\infty }$ は次のように定義される。

R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.

同様に、 $R_{A}^{\infty }$ は、ある定数K が存在して、すべてのリストLに対して次のようになる最小の数です。 ^{[ 4 ]}

A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K

。

さらに、すべての項目のサイズが最大で $\alpha$ このようなリストの場合、制限付きサイズのパフォーマンス比は次のように表されます。 $R_{A}({\text{size}}\leq \alpha )$ そして $R_{A}^{\infty }({\text{size}}\leq \alpha )$ 。

ビンパッキングの近似アルゴリズムは、2つのカテゴリに分類できます。

オンラインヒューリスティックは、指定された順序でアイテムを考慮し、それらを1つずつ容器の中に配置します。これらのヒューリスティックは、この問題のオフライン版にも適用可能です。
オフラインヒューリスティクスは、例えばアイテムをサイズ順に並べ替えるなどして、与えられたアイテムリストを変更します。これらのアルゴリズムは、この問題のオンライン版には適用できません。しかし、時間計算量が小さいという利点を維持しながら、近似保証が向上しています。オフラインヒューリスティクスのサブカテゴリとして、漸近近似スキームがあります。これらのアルゴリズムは、次の形式の近似保証を持ちます。 $(1+\varepsilon )\mathrm {OPT} (L)+C$ ある定数に依存するかもしれない $1/\varepsilon$ 任意の大きな $\mathrm {OPT} (L)$ これらのアルゴリズムは任意に近づき、 $\mathrm {OPT} (L)$ しかし、これはヒューリスティックなアプローチと比較して、（劇的に）時間計算量が増加するという代償を伴う。

オンラインヒューリスティクス

オンライン版のビンパッキング問題では、アイテムが次々と到着し、次のアイテムが何であるか、あるいは次のアイテムがあるかどうかも分からないまま、アイテムをどこに置くかという（不可逆的な）決定を下さなければなりません。ビンパッキングのためのオフラインおよびオンラインの多様なヒューリスティックが、デビッド・S・ジョンソンによって博士論文で研究されています。^{[ 11 ]}

単一クラスアルゴリズム

以下のような一般的なスキームを用いる単純なアルゴリズムは数多く存在する。

入力リストの各項目について：
1. もしその品物が現在空いている回収箱のいずれかに収まる場合は、それらの回収箱のいずれかに入れてください。
2. そうでない場合は、新しい容器を開けて、そこに新しい物を入れてください。

これらのアルゴリズムは、ステップ1で新しいアイテムを入れる空きビンを選択する基準が異なります（詳細については、リンク先のページを参照してください）。

Next Fit (NF)は常に 1 つのオープンビンを保持します。新しいアイテムがそれに収まらない場合、現在のビンを閉じて新しいビンを開きます。利点は、メモリに 1 つのオープンビンだけを保持すればよいため、空間が限定されたアルゴリズムであることです。欠点は、漸近近似比が 2 であることです。特に、 $NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$ 、そしてそれぞれについて $N\in \mathbb {N}$ リスト $L$ が存在し、 $\mathrm {OPT} (L)=N$ そして $NF(L)=2\cdot \mathrm {OPT} (L)-2$ ^{[ 11 ]}項目のサイズに基づいて、その漸近近似比をいくらか改善することができる。 $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2$ すべての人々のために $\alpha \geq 1/2$ そして $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )$ すべての人々のために $\alpha \leq 1/2$ AnyFitアルゴリズムである各アルゴリズム $Aについて、以下が成り立つ。$ $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )$ 。
Next-k-Fit (NkF)は Next-Fit の変種ですが、1 つのビンだけを開いたままにするのではなく、最後の $k$ 個のビンを開いたままにして、アイテムが収まる最初のビンを選択します。そのため、k 境界空間アルゴリズムと呼ばれます。^{[ 12 ]} $k\geq 2$ NkF は NF の結果と比較して改善された結果をもたらしますが、 $k を$ $2$ より大きい定数に増やしても、アルゴリズムの最悪ケースの動作はそれ以上改善されません。アルゴリズム $A$ が AlmostAnyFit アルゴリズムであり、 $m=\lfloor 1/\alpha \rfloor \geq 2$ それから $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m$ [ ¹¹^]
ファーストフィット（FF）は、開いた順にすべてのビンを開いたままにします。新しいアイテムは、最初に適合するビンに配置しようとします。その近似比は $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ 入力リストの族 $L$ が存在し、 $FF(L)$ この境界に一致する。^{[ 13 ]}
ベストフィット（BF）もすべてのビンを開いたままにしますが、新しいアイテムをそれぞれ、最大積載量のビンに収まるように配置しようとします。その近似比はFFと同じで、次のようになります。 $BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ 入力リストの族 $L$ が存在し、 $BF(L)$ この境界に一致する。^{[ 14 ]}
ワーストフィット（WF）は、各新しいアイテムを最小限の負荷でビンに配置しようとします。ネクストフィットと同様に動作が悪くなる可能性があり、その場合は最悪のケースのリストに表示されます。 $NF(L)=2\cdot \mathrm {OPT} (L)-2$ さらに、それは次のように主張する。 $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$ WFはAnyFitアルゴリズムであるため、次のようなAnyFitアルゴリズムが存在する。 $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$ [ ¹¹^]
ほぼ最悪適合 (AWF) は、新しいアイテムを2 番目に空いている空きビン (またはそのようなビンが 2 つある場合は最も空いているビン) に配置しようとします。収まらない場合は、最も空いているビンを試します。漸近的な最悪ケースの比率は、 ${\tfrac {17}{10}}$ [ ¹¹^]

これらの結果を一般化するために、ジョンソンは、any-fitアルゴリズムとalmost-any-fitアルゴリズムと呼ばれる2種類のオンラインヒューリスティクスを導入した。^{[ 4 ]}^{： 470}

AnyFit (AF)アルゴリズムでは、現在の空でないビンがB ₁ ,..., B _jである場合、現在のアイテムはB ₁ ,..., B _jのいずれにも収まらない場合を除き、B _{j +1}にパックされません。FF、WF、BF、および AWF アルゴリズムはこの条件を満たします。ジョンソンは、任意の AnyFit アルゴリズム A と任意の $\alpha$ :
$R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )$ 。
AlmostAnyFit (AAF)アルゴリズムにおいて、現在の空でないビンがB ₁ ,..., B _jであり、これらのビンの中でB _{k が}最小の負荷を持つ唯一のビンである場合、現在のアイテムは、左側のどのビンにも収まらない場合を除き、 B _kには詰め込まれません。FF、BF、AWF アルゴリズムはこの条件を満たしますが、WF は満たしません。ジョンソンは、任意の AAF アルゴリズム A と任意の $α$ に対して、次のことを証明しました。
$R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )$ 特に： $R_{A}^{\infty }=1.7$ 。

洗練されたアルゴリズム

AnyFit以外のヒューリスティックを用いることで、より精度の高い近似比率を実現できます。これらのヒューリスティックは通常、異なるサイズ範囲のアイテムに対応するために、複数のクラスのオープンビンを保持します（詳細については、リンク先のページを参照してください）。

改良型ファーストフィットビンパッキング（RFF）は、アイテムのサイズを4つの範囲に分割します。 $\left({\frac {1}{2}},1\right]$ 、 $\left({\frac {2}{5}},{\frac {1}{2}}\right]$ 、 $\left({\frac {1}{3}},{\frac {2}{5}}\right]$ 、そして $\left(0,{\frac {1}{3}}\right]$ 同様に、容器は4つのクラスに分類されます。次の項目 $i\in L$ はまず対応するクラスに割り当てられます。そのクラス内では、 first-fitを使用してビンに割り当てられます。このアルゴリズムは、現在のアイテムが開いているビンに収まる場合でも新しいビンを開く可能性があるため、Any-Fit アルゴリズムではないことに注意してください。このアルゴリズムは、Andrew Chi-Chih Yao ^{[ 15 ]}によって最初に発表され、近似保証があることを証明しました。 $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$ 。
ハーモニックkはサイズの区間を分割します $(0,1]$ ハーモニック進行に基づいて $k-1$ ピース $I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]$ のために $1\leq j<k$ そして $I_{k}:=\left(0,{\frac {1}{k}}\right]$ そのため $\bigcup _{j=1}^{k}I_{j}=(0,1]$ このアルゴリズムは、LeeとLeeによって最初に記述されました。^{[ 16 ]} 時間計算量は ${\mathcal {O}}(|L|\log(|L|))$ そして各ステップにおいて、アイテムを配置するために使用できる可能性のあるオープンビンは最大で $k個$ であり、つまり $k-$ 境界空間アルゴリズムである。 $k\rightarrow \infty$ 、その近似比は以下を満たす。 $R_{Hk}^{\infty }\approx 1.6910$ そして、漸近的にタイトである。
Refined-harmonic はHarmonic-k のアイデアとRefined-First-Fitのアイデアを組み合わせたものです。 ${\tfrac {1}{3}}$ Refined-First-Fitと同様ですが、より小さなアイテムはHarmonic-kを使用して配置されます。この戦略の直感は、より小さいアイテムを含むビンの膨大な無駄を減らすことです。 ${\tfrac {1}{2}}$ このアルゴリズムは、最初にLeeとLeeによって記述されました。^{[ 16 ]} 彼らは、 $k=20$ それは、 $R_{RH}^{\infty }\leq 373/228$ 。

オンラインアルゴリズムの一般的な下限値

Yao ^{[ 15 ]}は 1980 年に、漸近的な競争比がより小さいオンラインアルゴリズムは存在しないことを証明した。 ${\tfrac {3}{2}}$ Brown ^{[ 17 ]}と Liang ^{[ 18 ]}はこの境界を改善し、1.53635。その後、この上限は改善され、1.54014は van Vliet によって算出された。^{[ 19 ]}^{[ 20 ]} 2012 年に、この下限値は Békési と Galambos ^{[ 20 ]}によってさらに改善され、 ${\tfrac {248}{161}}\approx 1.54037$ 。

比較表

オフラインアルゴリズム

オフライン版のビンパッキングでは、アルゴリズムはアイテムをビンに配置する前にすべてのアイテムを確認できます。これにより、近似率を向上させることができます。

乗法近似

オフライン近似方式で用いられる最も単純な手法は以下のとおりです。

入力リストをサイズの降順で並べ替える。
順序付きリストに対してオンラインアルゴリズムを実行する。

ジョンソン^{[ 11 ]}は、降順で並べられたリスト上で実行される任意のAnyFitスキームAの漸近近似比が次のようになることを証明した。

$1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25$ 。

この系統のメソッドには以下のようなものがあります（詳細はリンク先のページをご覧ください）。

First-fit-decreasing (FFD)は、アイテムをサイズの降順で並べ替え、その後 First-Fit を呼び出します。その近似比は $FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$ 、これは厳しい。^{[ 23 ]}
Next-Fit-Decreasing (NFD)は、アイテムをサイズの降順で並べ替え、 Next-Fitを呼び出します。最悪の場合、その近似比率は 1.7 よりわずかに小さくなります。^{[ 24 ]}また、確率的に分析されています。^{[ 25 ]} Next-Fit は、リストとその逆を同じ数のビンに詰め込みます。したがって、Next-Fit-Increasing は Next-Fit-Decreasing と同じパフォーマンスになります。^{[ 26 ]}
修正ファーストフィット減少法(MFFD) ^{[ 27 ]}は、サイズによってアイテムを大、中、小、極小の 4 つのサイズクラスに分類することで、半分のビンより大きいアイテムに対する FFD を改善します。これは、それぞれサイズが 1/2 ビン、1/3 ビン、1/6 ビン、およびそれより小さいアイテムに対応します。その近似保証は $MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$ [ ²⁸^]

Fernandez de la VegaとLueker ^{[ 29 ]}は、ビンパッキングのためのPTASを発表した。 $\varepsilon >0$ 彼らのアルゴリズムは最大でサイズの解を見つける $(1+\varepsilon )\mathrm {OPT} +1$ そして時間通りに走る ${\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)$ 、どこ ${\mathcal {O}}_{\varepsilon }(1)$ 関数は、 $1/\varepsilon$ このアルゴリズムでは、適応型入力丸め法が考案されました。入力された数値はグループ化され、各グループの最大値に切り上げられます。これにより、異なるサイズの少数のインスタンスが生成され、構成線形計画法を使用して正確に解くことができます。^{[ 30 ]}

加法近似

カルマルカー・カルプのビンパッキングアルゴリズムは、最大で $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ 、そして $n$ の多項式時間で実行されます（多項式の次数は高く、少なくとも8です）。

Rothvoss ^{[ 31 ]}は、最大で $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ ゴミ箱。

HobergとRothvoss ^{[ 32 ]}はこのアルゴリズムを改良し、最大で $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))$ ビン。このアルゴリズムはランダム化されており、実行時間は $n$ の多項式です。

比較表

正確なアルゴリズム

マルテロとトス^{[ 34 ]}は、MTPと呼ばれる1次元ビンパッキング問題に対する正確なアルゴリズムを開発した。より高速な代替案は、 2002年にリチャード・E・コルフによって提案され^{[ 35 ]}、後に改良されたビン補完アルゴリズムである^{[ 36 ]。}

2013年にSchreiberとKorfによってさらなる改良が発表されました。^{[ 37 ]}新しい改良型ビン補完アルゴリズムは、100個のアイテムを持つ非自明な問題ではビン補完よりも最大5桁高速であることが示されており、最適解として20個未満のビンを持つ問題ではBelovとScheithauerによるBCP（分岐限定法）アルゴリズムよりも優れています。どのアルゴリズムが最も優れたパフォーマンスを発揮するかは、アイテム数、最適なビン数、最適解の未使用スペース、値の精度などの問題の特性に依存します。

様々なサイズのものが少数あります

ビンパッキングの特殊なケースとして、異なるサイズのアイテムが少数d個存在する場合が挙げられます。各サイズごとに多数の異なるアイテムが存在する可能性があります。このケースは高多重度ビンパッキングとも呼ばれ、一般的な問題よりも効率的なアルゴリズムが適用可能です。

断片化を伴うビンパッキング

断片化を伴うビンパッキング、または断片化可能なオブジェクトビンパッキングは、アイテムをパーツに分割し、各パーツを別々のビンに個別に配置できるビンパッキング問題の変種です。アイテムをパーツに分割することで、例えばビンの総数を最小化するなど、全体的なパフォーマンスを向上させることができます。さらに、最適化変数の一部が連続になるため、最適なスケジュールを見つける計算問題が容易になる可能性があります。一方、アイテムを分割するにはコストがかかる場合があります。この問題は、Mandal、Chakrabarti、およびGhoseによって最初に導入されました。^{[ 38 ]}

バリエーション

この問題には主に2つの種類がある。

最初の方式は、サイズ増加型断片化を伴うビンパッキング（BP-SIF）と呼ばれ、各アイテムが断片化される場合があり、各断片のサイズにオーバーヘッドユニットが加算されます。
2番目の方式は、サイズ保持型断片化によるビンパッキング（BP-SPF）と呼ばれ、各アイテムにはサイズとコストがあり、アイテムを断片化するとコストは増加するがサイズは変化しない。

計算複雑性

Mandal、Chakrabarti、Ghose ^{[ 38 ]}はBP-SPFがNP困難であることを証明した。

メナカーマンとロム^{[ 39 ]}は、BP-SIFとBP-SPFがどちらも強いNP困難であることを示した。困難であるにもかかわらず、彼らはいくつかのアルゴリズムを提示し、その性能を調査した。彼らのアルゴリズムは、ネクストフィットやファーストフィット減少などのビンパッキングの古典的なアルゴリズムを、アルゴリズムの基礎として使用している。

Bertazzi、Golden、Wang ^{[ 40 ]}は、BP-SIF の変種を導入し、 $1-x$ 分割ルール：アイテムは、そのサイズに応じて1つの方法でのみ分割できます。これは、例えば車両経路問題に役立ちます。彼らの論文では、このバリアントの最悪ケースのパフォーマンス限界が示されています。

Shachnai、Tamir、Yehezkeli ^{[ 41 ] は}、BP-SIF と BP-SPF の近似スキームを開発しました。デュアルPTAS (問題のデュアルバージョン用の PTAS)、APTAS と呼ばれる漸近 PTAS、および両方のバージョンに対する AFPTAS と呼ばれるデュアル漸近FPTAS です。

Ekici ^{[ 42 ]}は、一部のアイテムが競合し、競合するアイテムの断片を同じビンに詰め込むことが禁止されている BP-SPF の変種を導入しました。彼らは、この変種も NP 困難であることを証明しました。

CassazzaとCeselli ^{[ 43 ]}は、コストもオーバーヘッドもなく、ビンの数が固定されているバリアントを導入した。ただし、断片化の数は最小限に抑える必要がある。彼らは、厳密解と近似解の両方について、数理計画法アルゴリズムを提示している。

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

ビンパッキングの重要な特殊ケースは、アイテムサイズが割り切れる数列（因数分解とも呼ばれる）を形成する場合である。割り切れるアイテムサイズの特殊ケースは、コンピュータシステムのメモリ割り当てで発生し、アイテムサイズはすべて2のべき乗である。アイテムサイズが割り切れる場合、ビンパッキングのヒューリスティックアルゴリズムの一部は最適な解を見つける。^{[ 45 ]}

ビンに対するカーディナリティ制約

ビンパッキングには、ビンにカーディナリティ制約がある変種があります。各ビンには、固定された整数kに対して、最大でk 個のアイテムを含めることができます。

Krause、Shen、Schwetman ^{[ 46 ] は}、この問題を最適ジョブスケジューリングの変種として紹介しています。コンピュータにはk 個のプロセッサがあります。単位時間 (1) を要するn個のジョブがありますが、それぞれ異なるメモリ要件を持っています。各時間単位は単一のビンとみなされます。目標は、各ビンで実行されるジョブ数が最大k個になるようにしながら、使用するビン数 (=時間単位数) をできるだけ少なくすることです。彼らは、最大 k 個のジョブで解を見つけるためのいくつかのヒューリスティックアルゴリズムを提示しています。 $2\mathrm {OPT}$ ゴミ箱。
ケラーラーとプフェルシー^{[ 47 ]}は、実行時間 $O(n^{2}\log {n})$ 最大で $\left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil$ ビン。このアルゴリズムは、 OPT に対して二分探索を実行します。検索された値mごとに、アイテムを 3 m /2 個のビンに詰め込もうとします。

非加法関数

ビンパッキングモデルをより一般的なコスト関数や負荷関数に拡張する方法はいくつかあります。

Anily、Bramel、Simchi-Levi ^{[ 48 ]}は、ビンのコストがビン内のアイテム数の凹関数である設定を研究しています。目的は、ビンの数ではなく総コストを最小化することです。彼らは、 next-fit-increasing bin packing が、任意の凹関数かつ単調なコスト関数に対して、絶対的な最悪ケース近似比が最大で 7/4、漸近的な最悪ケース比が 1.691 を達成することを示しています。
Cohen、Keller、Mirrokni、Zadimoghaddam ^{[ 49 ] は}、アイテムのサイズが事前にわかっておらず、ランダム変数である設定を研究しています。これは、クラウドコンピューティング環境で特に一般的です。特定のユーザーが必要とするリソースの量には上限がありますが、ほとんどのユーザーは容量よりもはるかに少ないリソースしか使用しません。したがって、クラウドマネージャーは、わずかにオーバーコミットすることで大きな利益を得られる可能性があります。これにより、確率制約付きのビンパッキングの変種が導き出されます。各ビン内のサイズの合計が最大Bである確率は、少なくともpでなければなりません。ここで、pは固定定数です (標準のビンパッキングはp =1 に対応します)。彼らは、緩やかな仮定の下で、この問題は、各ビン内の「負荷」がアイテムの合計ではなく、その特定の劣モジュラ関数に等しい劣モジュラビンパッキング問題と同等であることを示しています。

リソース

BPPLIB - 調査、コード、ベンチマーク、ジェネレータ、ソルバー、および参考文献のライブラリ。

参考文献

↑マルテッロ、シルヴァーノ；トス、パオロ (1990)、「ビンパッキング問題」(PDF)、ナップサック問題：アルゴリズムとコンピュータ実装、チチェスター、英国：ジョン・ワイリー・アンド・サンズ、ISBN 04719242022006年5月8日にオリジナル（PDF）からアーカイブされました。
↑ Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing" . Combinatorial Optimization: Theory and Algorithms . Algorithms and Combinatorics 21. Springer. pp. 426–441 . doi : 10.1007/3-540-29297-7_18 . ISBN 978-3-540-25684-7。
↑ Barrington, David Mix (2006). "Bin Packing" . 2019年2月16日のオリジナルからアーカイブ済み。2016年2月27日取得。
1 2 3コフマンジュニア、エドワード G.チリク、ヤーノス。ガランボス、ガボール;マルテロ、シルバノ。 Vigo、Daniele (2013)、「ビンパッキング近似アルゴリズム: 調査と分類」、Pardalos、Panos M.杜、丁珠。 Graham、Ronald L. (編)、『Handbook of Combinatorial Optimization』、ニューヨーク、ニューヨーク州: Springer、pp. 455–531、doi : 10.1007/978-1-4419-7997-1_35、ISBN 978-1-4419-7997-12021年8月8日取得
↑ 「DHCPv6-PD - 最初のステップ」。 2024年6月12日取得。
↑ Lewis, R. (2009), "順序に依存しない最小グループ化問題に対する汎用ヒルクライミング法：グラフ彩色とビンパッキングの事例研究" (PDF) , Computers and Operations Research , 36 (7): 2295– 2310, doi : 10.1016/j.cor.2008.09.004 , S2CID 1577334
↑ Sindelar, Michael; Sitaraman, Ramesh K.; Shenoy, Prashant (2011). "仮想マシンのコロケーションのための共有認識アルゴリズム" . Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures . pp. 367–378 . doi : 10.1145/1989493.1989554 . ISBN 978-1-4503-0743-7。
1 2 3 Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (編). Computers and Intractability: A Guide to the Theory of NP-Completeness . A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338 . ISBN 0-7167-1045-5. MR 0519066 .
↑マーテロとトス、1990 年、p. 221
↑ Vazirani, Vijay V. (2013年3月14日).近似アルゴリズム. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Johnson, David S (1973). "ほぼ最適なビンパッキングアルゴリズム" (PDF) .マサチューセッツ工科大学.
↑ゴンザレス、テオフィロ F. (2018年5月23日).近似アルゴリズムとメタヒューリスティクスのハンドブック。第2巻現代的および新興の応用. Taylor & Francis Incorporated. ISBN 9781498770156。
1 2 3ドーサ、ジェルジュ;スガール、ジリ (2013)。「First Fit ビンのパッキング: 綿密な分析」。コンピュータサイエンスの理論的側面に関する第 30 回国際シンポジウム (STACS 2013)。２０． Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538– 549. doi : 10.4230/LIPIcs.STACS.2013.538。
1 2 3 György, Dósa; Sgall, Jirí (2014). "最適ビンパッキングの最適分析". Automata, Languages, and Programming . Lecture Notes in Computer Science. Vol. 8572. pp. 429–441 . doi : 10.1007/978-3-662-43948-7_36 . ISBN 978-3-662-43947-0。
1 2 3 4 5 Yao, Andrew Chi-Chih (1980 年 4 月) 「ビンパッキングのための新しいアルゴリズム」 Journal of the ACM 27 ( 2): 207–227 . doi : 10.1145/322186.322187 . S2CID 7903339 .
1 2 3 4 5 6 7 Lee, CC; Lee, DT (1985 年 7 月)。「シンプルなオンラインビンパッキングアルゴリズム」。Journal of the ACM。32 ( 3 ): 562–572。doi : 10.1145 /3828.3833。S2CID 15441740。
↑ Donna J, Brown (1979). "オンライン一次元ビンパッキングアルゴリズムの下限値" (PDF) .技術報告書. 2022年3月17日にオリジナルからアーカイブ(PDF) 。
↑ Liang, Frank M. (1980). "オンラインビンパッキングの下限". Information Processing Letters . 10 (2): 76–79 . doi : 10.1016/S0020-0190(80)90077-0 .
↑ van Vliet, André (1992). 「オンラインビンパッキングアルゴリズムの改善された下限」. Information Processing Letters . 43 (5): 277–284 . doi : 10.1016/0020-0190(92)90223-I .
1 2バログ、ヤーノス;ベケシ、ユジェフ。ガボール、ガランボス（2012 年 7 月）。「特定クラスのビンパッキングアルゴリズムの新しい下限」。理論的なコンピューターサイエンス。440 – 441: 1 – 13. doi : 10.1016/j.tcs.2012.04.017。
1 2 Ramanan, Prakash ; Brown, Donna J; Lee, CC; Lee, DT ( 1989 年 9 月) 。「線形時間でのオンラインビンパッキング」。Journal of Algorithms。10 ( 3 ): 305–326。doi : 10.1016/0196-6774(89)90031- X。hdl : 2142/74206。
1 2 3 Seiden, Steven S. (2002). 「オンラインビンパッキング問題について」。Journal of the ACM . 49 (5): 640– 671. doi : 10.1145/585265.585269 . S2CID 14164016 .
1 2 3 Dósa, György (2007). "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE . doi : 10.1007/978-3-540-74450-4_1 .
↑ Baker, BS; Coffman, Jr., EG (1981-06-01). "A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing" . SIAM Journal on Algebraic and Discrete Methods . 2 (2): 147– 152. doi : 10.1137/0602019 . ISSN 0196-5212 . {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
↑ Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "A probabilistic analysis of the next fit decreasing bin packing heuristic" . Operations Research Letters . 5 (5): 233– 236. doi : 10.1016/0167-6377(86)90013-1 . hdl : 1765/11645 . ISSN 0167-6377 . S2CID 50663185 .
↑ Fisher, David C. (1988-12-01). "Next-fit packs a list and its reverse into the same number of bins" . Operations Research Letters . 7 (6): 291– 293. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .
1 2 Johnson, David S; Garey, Michael R (1985 年 10 月). "ビンパッキングに関する 7160 定理" . Journal of Complexity . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .
1 2 Yue, Minyi; Zhang, Lei (1995 年 7 月). "MFFD ビンパッキングアルゴリズムに対する不等式 MFFD(L) ≤ 71/60 OPT(L) + 1,L の簡単な証明". Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi : 10.1007/BF02011198 . S2CID 118263129 .
↑ Fernandez de la Vega, W.; Lueker, GS (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica . 1 (4): 349– 355. doi : 10.1007/BF02579456 . ISSN 1439-6912 . S2CID 10519631 .
↑ Claire Mathieu。「近似アルゴリズムパート I、第 3 週: ビンパッキング」。Coursera。2021年 7 月15日のオリジナルからアーカイブ済み。
1 2 Rothvoß, T. (2013-10-01). "O(log OPT · Log Log OPT) ビン内でのビンパッキングの近似". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 20–29 . arXiv : 1301.4010 . doi : 10.1109/FOCS.2013.11 . ISBN 978-0-7695-5135-7. S2CID 15905063 .
1 2 Hoberg, Rebecca; Rothvoss, Thomas (2017), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , SIAM, pp. 2616–2625 , arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2S2CID 1647463
↑ Karmarkar, Narendra; Karp, Richard M. (1982年11月) 「一次元ビンパッキング問題に対する効率的な近似スキーム」 .第23回コンピュータサイエンス基礎に関する年次シンポジウム (SFCS 1982) . pp. 312–320 . doi : 10.1109/SFCS.1982.61 . S2CID 18583908 .
↑ Martello & Toth 1990 、pp. 237–240。
↑ Korf, Richard E. (2002).最適なビンパッキングのための新しいアルゴリズム(PDF) . AAAI-02.
↑ Richard E. Korf (2003)、「最適なビンパッキングのための改良アルゴリズム」、人工知能に関する国際合同会議議事録（pp. 1252–1258）
↑ Schreiber, Ethan L.; Korf, Richard E. (2013), "Improved Bin Completion for Optimal Bin Packing and Number Partitioning" (PDF) , Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence , IJCAI '13, Beijing, China: AAAI Press, pp. 651–658 , ISBN 978-1-57735-633-2
1 2 Mandal, CA; Chakrabarti, PP; Ghose, S. (1998-06-01). "Complexity of fragmentable object bin packing and an application" . Computers & Mathematics with Applications . 35 (11): 91– 97. doi : 10.1016/S0898-1221(98)00087-X . ISSN 0898-1221 .
↑ Nir Menakerman および Raphael Rom「アイテム断片化によるビンパッキング」。アルゴリズムとデータ構造、第 7 回国際ワークショップ、WADS 2001、米国ロードアイランド州プロビデンス、2001 年 8 月 8 ～ 10 日、議事録。
↑ Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (2019-05-31). "アイテム断片化を伴うビンパッキング問題：最悪ケース分析" . Discrete Applied Mathematics . GO X Meeting、Rigi Kaltbad (CH)、2016年7月10日～14日。261 : 63– 77. doi : 10.1016 /j.dam.2018.08.023 . ISSN 0166-218X . S2CID 125361557 .
↑ Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). "アイテム断片化を伴うパッキングの近似スキーム" . Erlebach, Thomas; Persinao, Giuseppe (編).近似とオンラインアルゴリズム. Lecture Notes in Computer Science. Vol. 3879. Berlin, Heidelberg: Springer. pp. 334–347 . doi : 10.1007/11671411_26 . ISBN 978-3-540-32208-5。
↑ Ekici, Ali (2021-02-01). "競合とアイテムの断片化を伴うビンパッキング問題" . Computers & Operations Research . 126 105113. doi : 10.1016/j.cor.2020.105113 . ISSN 0305-0548 . S2CID 225002556 .
↑ Casazza, Marco; Ceselli, Alberto (2014-06-01). "アイテム断片化を伴うビンパッキング問題のための数理計画アルゴリズム" . Computers & Operations Research . 46 : 1– 11. doi : 10.1016/j.cor.2013.12.008 . ISSN 0305-0548 .
↑ Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (2019-03-16). "Integer optimization with penalized fractional values: The Knapsack case" . European Journal of Operational Research . 273 (3): 874– 888. doi : 10.1016/j.ejor.2018.09.020 . hdl : 11585/657029 . ISSN 0377-2217 . S2CID 31722681 .
↑ 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 .
↑ Krause, KL; Shen, VY; Schwetman, HD (1975-10-01). "マルチプログラミングコンピュータシステムのモデルに対するいくつかのタスクスケジューリングアルゴリズムの分析" . Journal of the ACM . 22 (4): 522– 550. doi : 10.1145/321906.321917 . ISSN 0004-5411 . S2CID 10214857 .
↑ Kellerer, H.; Pferschy, U. (1999-01-01). "Cardinality constrained bin-packing problems" . Annals of Operations Research . 92 : 335–348 . doi : 10.1023/A:1018947117526 . ISSN 1572-9338 . S2CID 28963291 .
1 2 Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "一般的なコスト構造を持つビンパッキング問題のヒューリスティクスの最悪ケース分析" . Operations Research . 42 (2): 287– 298. doi : 10.1287/opre.42.2.287 . ISSN 0030-364X .
↑ Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (2019-07-01). "クラウドサービスにおける過剰コミットメント: 確率制約付きビンパッキング" . Management Science . 65 (7): 3255– 3271. arXiv : 1705.09335 . doi : 10.1287/mnsc.2018.3091 . ISSN 0025-1909 . S2CID 159270392 .
↑ Johnson, David S. (2016), "Vector Bin Packing" , Kao, Ming-Yang (編), Encyclopedia of Algorithms , New York, NY: Springer New York, pp. 2319–2323 , doi : 10.1007/978-1-4939-2864-4_495 , ISBN 978-1-4939-2863-72025年5月15日取得
↑ Chung, Yerim; Park, Myoung-Ju (2015-01-01). "逆ビンパッキング問題に関する注記" . Information Processing Letters . 115 (1): 60– 68. doi : 10.1016/j.ipl.2014.09.005 . ISSN 0020-0190 .
↑ボヤール、ジョアン;エプスタイン、リア。ファヴホルト、リーン・M.コルト、イェンス・Ｓ．ラーセン、キム・S.ペダーセン、モーテン M.ウォールク、サンネ (2006-10-11)。「リソースビンの最大パッキング問題」。理論的なコンピューターサイエンス。362 (1): 127–139。土井: 10.1016/j.tcs.2006.06.001。ISSN 0304-3975。
↑ Huang, Xin; Lu, Pinyan (2020-11-10). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". arXiv : 1907.04505 [ cs.GT ].
↑ Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). "利己的なビンパッキング問題に関する注記" . Journal of Global Optimization . 56 (4): 1457– 1462. doi : 10.1007/s10898-012-9856-9 . ISSN 0925-5001 . S2CID 3082040 .
↑ 「3Dビンパッキング：物流のテトリス」。www.optioryx.com 。 2026年1月6日取得。
↑ Lodi A., Martello S., Monaci, M., Vigo, D. (2010) 「2次元ビンパッキング問題」 V.Th. Paschos (編)『組合せ最適化のパラダイム』 Wiley/ISTE、pp. 107–129
↑ Kanavathy LR、Dube E. (2006) 第6回IASTED国際モデリング、シミュレーション、最適化会議議事録、MSOシミュレーションによる3次元ビンパッキングの最適化
↑ Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms" . 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) . pp. 298–302 . doi : 10.1109/BICTA.2010.5645312 . ISBN 978-1-4244-6437-1。

[1] マルテッロ、シルヴァーノ；トス、パオロ (1990)、「ビンパッキング問題」(PDF)、ナップサック問題：アルゴリズムとコンピュータ実装、チチェスター、英国：ジョン・ワイリー・アンド・サンズ、ISBN 04719242022006年5月8日にオリジナル（PDF）からアーカイブされました。

[2] Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing" . Combinatorial Optimization: Theory and Algorithms . Algorithms and Combinatorics 21. Springer. pp. 426–441 . doi : 10.1007/3-540-29297-7_18 . ISBN 978-3-540-25684-7。

[3] Barrington, David Mix (2006). "Bin Packing" . 2019年2月16日のオリジナルからアーカイブ済み。2016年2月27日取得。

[:0-4] 1 2 3コフマンジュニア、エドワード G.チリク、ヤーノス。ガランボス、ガボール;マルテロ、シルバノ。 Vigo、Daniele (2013)、「ビンパッキング近似アルゴリズム: 調査と分類」、Pardalos、Panos M.杜、丁珠。 Graham、Ronald L. (編)、『Handbook of Combinatorial Optimization』、ニューヨーク、ニューヨーク州: Springer、pp. 455–531、doi : 10.1007/978-1-4419-7997-1_35、ISBN 978-1-4419-7997-12021年8月8日取得

[5] 「DHCPv6-PD - 最初のステップ」。 2024年6月12日取得。

[6] Lewis, R. (2009), "順序に依存しない最小グループ化問題に対する汎用ヒルクライミング法：グラフ彩色とビンパッキングの事例研究" (PDF) , Computers and Operations Research , 36 (7): 2295– 2310, doi : 10.1016/j.cor.2008.09.004 , S2CID 1577334

[7] Sindelar, Michael; Sitaraman, Ramesh K.; Shenoy, Prashant (2011). "仮想マシンのコロケーションのための共有認識アルゴリズム" . Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures . pp. 367–378 . doi : 10.1145/1989493.1989554 . ISBN 978-1-4503-0743-7。

[GareyJohnson2-8] 1 2 3 Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (編). Computers and Intractability: A Guide to the Theory of NP-Completeness . A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338 . ISBN 0-7167-1045-5. MR 0519066 .

[Martello19902-9] マーテロとトス、1990 年、p. 221

[10] Vazirani, Vijay V. (2013年3月14日).近似アルゴリズム. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657。

[johnson732-11] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Johnson, David S (1973). "ほぼ最適なビンパッキングアルゴリズム" (PDF) .マサチューセッツ工科大学.

[12] ゴンザレス、テオフィロ F. (2018年5月23日).近似アルゴリズムとメタヒューリスティクスのハンドブック。第2巻現代的および新興の応用. Taylor & Francis Incorporated. ISBN 9781498770156。

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

[DósaSgall142-14] 1 2 3 György, Dósa; Sgall, Jirí (2014). "最適ビンパッキングの最適分析". Automata, Languages, and Programming . Lecture Notes in Computer Science. Vol. 8572. pp. 429–441 . doi : 10.1007/978-3-662-43948-7_36 . ISBN 978-3-662-43947-0。

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

[LeeLee19852-16] 1 2 3 4 5 6 7 Lee, CC; Lee, DT (1985 年 7 月)。「シンプルなオンラインビンパッキングアルゴリズム」。Journal of the ACM。32 ( 3 ): 562–572。doi : 10.1145 /3828.3833。S2CID 15441740。

[17] Donna J, Brown (1979). "オンライン一次元ビンパッキングアルゴリズムの下限値" (PDF) .技術報告書. 2022年3月17日にオリジナルからアーカイブ(PDF) 。

[18] Liang, Frank M. (1980). "オンラインビンパッキングの下限". Information Processing Letters . 10 (2): 76–79 . doi : 10.1016/S0020-0190(80)90077-0 .

[19] van Vliet, André (1992). 「オンラインビンパッキングアルゴリズムの改善された下限」. Information Processing Letters . 43 (5): 277–284 . doi : 10.1016/0020-0190(92)90223-I .

[bbg-20] 1 2バログ、ヤーノス;ベケシ、ユジェフ。ガボール、ガランボス（2012 年 7 月）。「特定クラスのビンパッキングアルゴリズムの新しい下限」。理論的なコンピューターサイエンス。440 – 441: 1 – 13. doi : 10.1016/j.tcs.2012.04.017。

[RamananBLL19892-21] 1 2 Ramanan, Prakash ; Brown, Donna J; Lee, CC; Lee, DT ( 1989 年 9 月) 。「線形時間でのオンラインビンパッキング」。Journal of Algorithms。10 ( 3 ): 305–326。doi : 10.1016/0196-6774(89)90031- X。hdl : 2142/74206。

[Seiden20022-22] 1 2 3 Seiden, Steven S. (2002). 「オンラインビンパッキング問題について」。Journal of the ACM . 49 (5): 640– 671. doi : 10.1145/585265.585269 . S2CID 14164016 .

[Dosa072-23] 1 2 3 Dósa, György (2007). "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE . doi : 10.1007/978-3-540-74450-4_1 .

[24] Baker, BS; Coffman, Jr., EG (1981-06-01). "A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing" . SIAM Journal on Algebraic and Discrete Methods . 2 (2): 147– 152. doi : 10.1137/0602019 . ISSN 0196-5212 . {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[25] Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "A probabilistic analysis of the next fit decreasing bin packing heuristic" . Operations Research Letters . 5 (5): 233– 236. doi : 10.1016/0167-6377(86)90013-1 . hdl : 1765/11645 . ISSN 0167-6377 . S2CID 50663185 .

[26] Fisher, David C. (1988-12-01). "Next-fit packs a list and its reverse into the same number of bins" . Operations Research Letters . 7 (6): 291– 293. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[JohnsonGarey19852-27] 1 2 Johnson, David S; Garey, Michael R (1985 年 10 月). "ビンパッキングに関する 7160 定理" . Journal of Complexity . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .

[YueZhang19952-28] 1 2 Yue, Minyi; Zhang, Lei (1995 年 7 月). "MFFD ビンパッキングアルゴリズムに対する不等式 MFFD(L) ≤ 71/60 OPT(L) + 1,L の簡単な証明". Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi : 10.1007/BF02011198 . S2CID 118263129 .

[29] Fernandez de la Vega, W.; Lueker, GS (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica . 1 (4): 349– 355. doi : 10.1007/BF02579456 . ISSN 1439-6912 . S2CID 10519631 .

[30] Claire Mathieu。「近似アルゴリズムパート I、第 3 週: ビンパッキング」。Coursera。2021年 7 月15日のオリジナルからアーカイブ済み。

[:2-31] 1 2 Rothvoß, T. (2013-10-01). "O(log OPT · Log Log OPT) ビン内でのビンパッキングの近似". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 20–29 . arXiv : 1301.4010 . doi : 10.1109/FOCS.2013.11 . ISBN 978-0-7695-5135-7. S2CID 15905063 .

[:3-32] 1 2 Hoberg, Rebecca; Rothvoss, Thomas (2017), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , SIAM, pp. 2616–2625 , arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2S2CID 1647463

[:1-33] Karmarkar, Narendra; Karp, Richard M. (1982年11月) 「一次元ビンパッキング問題に対する効率的な近似スキーム」 .第23回コンピュータサイエンス基礎に関する年次シンポジウム (SFCS 1982) . pp. 312–320 . doi : 10.1109/SFCS.1982.61 . S2CID 18583908 .

[34] Martello & Toth 1990 、pp. 237–240。

[35] Korf, Richard E. (2002).最適なビンパッキングのための新しいアルゴリズム(PDF) . AAAI-02.

[Korf2003Korf2-36] Richard E. Korf (2003)、「最適なビンパッキングのための改良アルゴリズム」、人工知能に関する国際合同会議議事録（pp. 1252–1258）

[37] Schreiber, Ethan L.; Korf, Richard E. (2013), "Improved Bin Completion for Optimal Bin Packing and Number Partitioning" (PDF) , Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence , IJCAI '13, Beijing, China: AAAI Press, pp. 651–658 , ISBN 978-1-57735-633-2

[:03-38] 1 2 Mandal, CA; Chakrabarti, PP; Ghose, S. (1998-06-01). "Complexity of fragmentable object bin packing and an application" . Computers & Mathematics with Applications . 35 (11): 91– 97. doi : 10.1016/S0898-1221(98)00087-X . ISSN 0898-1221 .

[39] Nir Menakerman および Raphael Rom「アイテム断片化によるビンパッキング」。アルゴリズムとデータ構造、第 7 回国際ワークショップ、WADS 2001、米国ロードアイランド州プロビデンス、2001 年 8 月 8 ～ 10 日、議事録。

[40] Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (2019-05-31). "アイテム断片化を伴うビンパッキング問題：最悪ケース分析" . Discrete Applied Mathematics . GO X Meeting、Rigi Kaltbad (CH)、2016年7月10日～14日。261 : 63– 77. doi : 10.1016 /j.dam.2018.08.023 . ISSN 0166-218X . S2CID 125361557 .

[41] Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). "アイテム断片化を伴うパッキングの近似スキーム" . Erlebach, Thomas; Persinao, Giuseppe (編).近似とオンラインアルゴリズム. Lecture Notes in Computer Science. Vol. 3879. Berlin, Heidelberg: Springer. pp. 334–347 . doi : 10.1007/11671411_26 . ISBN 978-3-540-32208-5。

[42] Ekici, Ali (2021-02-01). "競合とアイテムの断片化を伴うビンパッキング問題" . Computers & Operations Research . 126 105113. doi : 10.1016/j.cor.2020.105113 . ISSN 0305-0548 . S2CID 225002556 .

[43] Casazza, Marco; Ceselli, Alberto (2014-06-01). "アイテム断片化を伴うビンパッキング問題のための数理計画アルゴリズム" . Computers & Operations Research . 46 : 1– 11. doi : 10.1016/j.cor.2013.12.008 . ISSN 0305-0548 .

[44] Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (2019-03-16). "Integer optimization with penalized fractional values: The Knapsack case" . European Journal of Operational Research . 273 (3): 874– 888. doi : 10.1016/j.ejor.2018.09.020 . hdl : 11585/657029 . ISSN 0377-2217 . S2CID 31722681 .

[:022-45] 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 .

[46] Krause, KL; Shen, VY; Schwetman, HD (1975-10-01). "マルチプログラミングコンピュータシステムのモデルに対するいくつかのタスクスケジューリングアルゴリズムの分析" . Journal of the ACM . 22 (4): 522– 550. doi : 10.1145/321906.321917 . ISSN 0004-5411 . S2CID 10214857 .

[47] Kellerer, H.; Pferschy, U. (1999-01-01). "Cardinality constrained bin-packing problems" . Annals of Operations Research . 92 : 335–348 . doi : 10.1023/A:1018947117526 . ISSN 1572-9338 . S2CID 28963291 .

[pubsonline.informs.org-48] 1 2 Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "一般的なコスト構造を持つビンパッキング問題のヒューリスティクスの最悪ケース分析" . Operations Research . 42 (2): 287– 298. doi : 10.1287/opre.42.2.287 . ISSN 0030-364X .

[49] Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (2019-07-01). "クラウドサービスにおける過剰コミットメント: 確率制約付きビンパッキング" . Management Science . 65 (7): 3255– 3271. arXiv : 1705.09335 . doi : 10.1287/mnsc.2018.3091 . ISSN 0025-1909 . S2CID 159270392 .

[50] Johnson, David S. (2016), "Vector Bin Packing" , Kao, Ming-Yang (編), Encyclopedia of Algorithms , New York, NY: Springer New York, pp. 2319–2323 , doi : 10.1007/978-1-4939-2864-4_495 , ISBN 978-1-4939-2863-72025年5月15日取得

[51] Chung, Yerim; Park, Myoung-Ju (2015-01-01). "逆ビンパッキング問題に関する注記" . Information Processing Letters . 115 (1): 60– 68. doi : 10.1016/j.ipl.2014.09.005 . ISSN 0020-0190 .

[:02-52] ボヤール、ジョアン;エプスタイン、リア。ファヴホルト、リーン・M.コルト、イェンス・Ｓ．ラーセン、キム・S.ペダーセン、モーテン M.ウォールク、サンネ (2006-10-11)。「リソースビンの最大パッキング問題」。理論的なコンピューターサイエンス。362 (1): 127–139。土井: 10.1016/j.tcs.2006.06.001。ISSN 0304-3975。

[53] Huang, Xin; Lu, Pinyan (2020-11-10). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". arXiv : 1907.04505 [ cs.GT ].

[54] Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). "利己的なビンパッキング問題に関する注記" . Journal of Global Optimization . 56 (4): 1457– 1462. doi : 10.1007/s10898-012-9856-9 . ISSN 0925-5001 . S2CID 3082040 .

[55] 「3Dビンパッキング：物流のテトリス」。www.optioryx.com 。 2026年1月6日取得。

[56] Lodi A., Martello S., Monaci, M., Vigo, D. (2010) 「2次元ビンパッキング問題」 V.Th. Paschos (編)『組合せ最適化のパラダイム』 Wiley/ISTE、pp. 107–129

[57] Kanavathy LR、Dube E. (2006) 第6回IASTED国際モデリング、シミュレーション、最適化会議議事録、MSOシミュレーションによる3次元ビンパッキングの最適化

[58] Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms" . 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) . pp. 298–302 . doi : 10.1109/BICTA.2010.5645312 . ISBN 978-1-4244-6437-1。

[ 1 ]

[ 2 ]

[ 3 ]

[ 5 ]

[

仮想

[ 8 ]

9

10 ]すべて

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

28

[ 29 ]

[ 30 ]

[ 34 ]

[ 35 ]

[ 36 ]。

[ 37 ]

[ 39 ]

[ 40 ]

[ 41 ] は

[ 42 ]

[ 43 ]

[ 44 ]

[ 46 ] は

[ 47 ]

[ 48 ]

[ 49 ] は

50

[ 51 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

58