ビンカバーの問題

コンテンツへジャンプ

メインメニュー

メインメニュー

サイドバーに移動隠れる

ナビゲーション

• メインページ
• コンテンツ
• 時事問題
• ランダム記事
• Wikipediaについて
• お問い合わせ

貢献する

• ヘルプ
• 編集方法を学ぶ
• コミュニティポータル
• 最近の変更
• ファイルをアップロード
• 特別ページ

検索

検索

外観

• 寄付する
• アカウントを作成する
• ログイン

個人用ツール

• 寄付する
• アカウントを作成する
• ログイン

コンテンツ

サイドバーに移動隠れる

• （トップ）
• 1双方向ビンフィリングアルゴリズム
  双方向ビンフィリングアルゴリズムのサブセクションを切り替える
  • 1.1証明
  • 1.2気密性
• 2 3クラスビンフィリングアルゴリズム
• 3多項式時間近似スキーム
• 4分割可能なアイテムサイズのパフォーマンス
• 5関連する問題
• 6つの実装
• 7参考文献

目次を切り替える

1つの言語

• スペイン語

リンクを編集

• 記事
• 話す

英語

• 読む
• 編集
• 履歴を表示

ツール

ツール

サイドバーに移動隠れる

アクション

• 読む
• 編集
• 履歴を表示

一般的な

• ここへのリンク
• 関連する変更
• ファイルをアップロード
• パーマリンク
• ページ情報
• このページを引用する
• 短縮URLを取得する
• QRコードをダウンロード

印刷/エクスポート

• PDFとしてダウンロード
• 印刷可能なバージョン

他のプロジェクト

• ウィキデータ項目

外観

サイドバーに移動隠れる

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

最大数のビンにアイテムを詰めるオペレーションズリサーチの問題

ビンカバーリング問題では、異なるサイズのアイテムを、使用されるビンの数を最大化する方法を使用して 、各ビンまたはコンテナーの合計サイズが少なくとも一定以上である有限の数のビンまたはコンテナーに詰め込む必要があります。

この問題はビンパッキング問題の双対です。ビンカバリングでは、ビンのサイズは下から制限され、その数は最大化することが目標です。ビンパッキングでは、ビンのサイズは上から制限され、その数は最小化することが目標です。^{[ 1 ]}

この問題はNP困難ですが、さまざまな効率的な近似アルゴリズムがあります。

• 最適なビンの少なくとも1/2、2/3、または3/4をカバーするアルゴリズムは、それぞれ時間とともに漸近的にカウントされます。^{[ 1 ] [ 2 ]} ${\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}$
• 漸近的PTAS、いくつかの離散分布に対して漸近的に最適な期待挙動を示す有界最悪ケース挙動を持つアルゴリズム、およびすべての離散分布に対して漸近的に最適な期待挙動を示す学習アルゴリズム。^{[ 3 ]}
• 漸近的FPTAS。^{[ 4 ]}

双方向ビンフィリングアルゴリズム

[編集]

Csirik, Frenk, Lebbe, Zhang ^{[ 2 ] : 16–19 は}、2/3近似のための以下の単純なアルゴリズムを提示している。ビンサイズが1で、アイテム数がn個であるとする。

• 項目を最大(1)から最小( n )の順に並べます。
• ビンを最大のアイテム1、2、...、mで埋めます。ここで、mはアイテム 1、...、 mの合計が1 未満となる最大の整数です。
• このビンに、値が 1 を超えるまで、n、n -1、... という最小の項目を追加します。

任意のインスタンスIについて、最適解におけるビンの数を 、双方向充填アルゴリズムにおけるビンの数を と表記します。この場合 、 、または同等の となります 。 ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {BDF} (I)}$ ${\displaystyle \mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)}$ ${\displaystyle \mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1}$

証拠

[編集]

証明には次の用語が使用されます。

• ${\displaystyle t:=\mathrm {BDF} (I)=}$アルゴリズムによって埋められたビンの数。
• ${\displaystyle B_{1},\ldots ,B_{t}:=}$アルゴリズムによって埋められたtビン。
• 初期項目-各tビンに最初に挿入されるt個の項目。
• 最終項目-各tビンに最後に挿入されるt個の項目。
• 中間項目- 最初でも最後でもないすべての項目。
• ${\displaystyle w}$ := 最大 1/2 である最終項目の数 (つまり、1/2 より大きい最終項目の数)。 ${\displaystyle t-w}$

各ビンの合計は少なくとも1ですが、最後のアイテムを除いた場合、残りの合計は1より小さくなります。最初のビン にはそれぞれ、最初のアイテム、場合によっては中間のアイテム、そして最後のアイテムが含まれます。最後のビンにはそれぞれ、最初のアイテムと最後のアイテムのみが含まれます。これは、どちらも1/2より大きく、合計が既に1より大きいためです。 ${\displaystyle B_{1},\ldots ,B_{t}}$ ${\displaystyle w}$ ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle t-w}$ ${\displaystyle B_{w+1},\ldots ,B_{t}}$

証明では2つのケースを検討します。

簡単なケースは、つまり、すべての最終アイテムが 1/2 より小さい場合です。この場合、すべての充填されたアイテムの合計は最大で 3/2 となり、残りのアイテムの合計は最大で 1 となるため、すべてのアイテムの合計は最大で となります 。一方、最適解では、すべてのビンの合計は少なくとも 1 となるため、すべてのアイテムの合計は少なくとも となります。したがって、要求どおりとなります。 ${\displaystyle w=t}$ ${\displaystyle B_{i}}$ ${\displaystyle 3t/2+1}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2+1}$

難しいケースは、つまり、いくつかの最終項目が 1/2 より大きい場合です。ここで、 の上限を、以下の和として表すことで 証明します。 ${\displaystyle w<t}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|}$

• ${\displaystyle K_{0}:=}$最初/最後のアイテムがない（中間のアイテムのみ）最適なビン。
• ${\displaystyle K_{1}:=}$ちょうど 1 つの初期/最終項目 (およびいくつかの中間項目) を含む最適なビン。
• ${\displaystyle K_{2}:=}$2 つ以上の初期/最終項目 (およびいくつかの中間項目) を含む最適なビン。

まず、およびにおける最適なビンに注目します 。各ビン内のアイテムと、少なくとも同等の価値がある におけるいくつかのアイテムとの間の一対一写像を提示します。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{t}}$

• ビン内の最初の/最後の単一のアイテムは、 の最初のアイテムにマッピングされます。これらは最大の最初のアイテムであることに注意してください。 ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$
• ビンとビンの中央のアイテムは、ビンの中央のアイテムにマッピングされます。これらのビンにはすべての中央のアイテムが含まれていることに注意してください。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{w}}$
• したがって、およびのすべての項目は、のすべての最終でない項目と、 のすべての中間項目にマッピングされます。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$
• 各ビンの最終項目を除く合計は 1未満です。さらに、最初の項目は1/2より大きいため、中間項目のみの合計は1/2未満です。したがって、 内の最終項目以外のすべての項目と 内の中間項目すべての合計は、最大で になります。 ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$ ${\displaystyle |K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2}$
• 各最適ビンの合計は少なくとも 1 です。したがって、 となり、 が成り立ちます。 ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2}$ ${\displaystyle 2|K_{0}|+|K_{1}|\leq w\leq t}$

ここでは、およびにおける最適なビンに焦点を当てます。 ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$

• ビンとビン内の初期/最終アイテムの総数は少なくとも 個ですが、各ビンには初期/最終アイテムがちょうど2個ずつあるため、それらの総数も 個になります。したがって、 となります。 ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$ ${\displaystyle |K_{1}|+2|K_{2}|}$ ${\displaystyle 2t}$ ${\displaystyle |K_{1}|+2|K_{2}|\leq 2t}$
• 後者の 2 つの不等式を合計すると となり、 が成り立ちます。 ${\displaystyle 2\mathrm {OPT} (I)\leq 3t}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2}$

締め付け感

[編集]

BDFでは2/3係数は厳しすぎます。次の例（ただしは十分に小さい）を考えてみましょう。BDFは最初のビンを最大のアイテムで初期化し、それを最小のアイテムで埋めます。すると、残りのアイテムは3つ組のビンしか埋めることができず、結果としてすべてのビンが埋められます。しかしOPTでは、各ビンに中サイズのアイテム2つと小さなアイテム2つを含めて埋めることができます。 ${\displaystyle \epsilon >0}$ $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}}$$ ${\displaystyle 6k}$ ${\displaystyle 6k}$ ${\displaystyle 2k+1}$ ${\displaystyle 3k}$

3クラスビンフィリングアルゴリズム

[編集]

Csirik、Frenk、Lebbe、Zhang ^{[ 2 ] : 19–24 は}、3/4近似を達成する別のアルゴリズムを提示している。このアルゴリズムは、アイテムを大きいものから小さいものの順に並べ、3つのクラスに分割する。

• X: サイズが少なくとも 1/2 のアイテム。
• Y: サイズが1/2未満かつ1/3以上のアイテム。
• Z: サイズが1/3未満のアイテム。

アルゴリズムは2つのフェーズで動作します。フェーズ1:

• Xの最大値、またはYの最大値2つのうち、どちらか大きい方の値で新しいビンを初期化します。どちらの場合も、初期のビンの合計は1未満であることに注意してください。
• 新しいビンに、Z から値の昇順でアイテムを入力します。
• XUY または Z のいずれかが空になるまで繰り返します。

フェーズ2:

• XUY が空の場合、単純な次適合ルールに従って、ビンを Z からのアイテムで埋めます。
• Z が空の場合、X に残っているアイテムを 2 つずつパックし、Y に残っているアイテムを 3 つずつパックします。

上記の例では、BDF のタイトネスを示し、セットは次のようになります。TCFは、すべてのビンを Y のアイテムのペアで初期化し、それらを Z のアイテムのペアで埋めるため、最適な結果を実現します。 $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots |Z|=6k\cdots \}\end{aligned}}}$$ ${\displaystyle 3k}$

任意のインスタンスIについて、最適解におけるビンの数を 、3クラス充填アルゴリズムにおける完全なビンの数 を とします。 ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {TCF} (I)}$ ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)}$

TCFの3/4係数は厳しすぎます。次の例を考えてみましょう（ただし、は十分に小さいです）。 ${\displaystyle \epsilon >0}$

$${\displaystyle {\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}}$$

TCFでは、最初のビンを最大の2つのアイテムで初期化し、そこに最小のアイテムを配置します。残りのアイテムは4つずつのグループでしかビンをカバーできないため、すべてのビンが埋められます。一方、OPTでは、各ビンに中サイズのアイテム3つと小サイズのアイテム3つずつを配置してビンを埋めることができます。 ${\displaystyle 12k}$ ${\displaystyle 12k}$ ${\displaystyle 3k+1}$ ${\displaystyle 4k}$

多項式時間近似スキーム

[編集]

Csirik、Johnson、Kenyon ^{[ 3 ]}は漸近的PTASを提示している。これは、すべてのε >0 に対して、すべての項目の合計が より大きい場合は少なくとも 個のビンを埋め、そうでない場合は少なくとも 個のビンを埋めるアルゴリズムである。実行時間は である。このアルゴリズムは、変数と制約を持つ構成線形計画の変形を解きます。このアルゴリズムは理論的にのみ興味深い。なぜなら、3/4 より優れた近似値を得るためには を取る必要があり、その場合変数の数は 個を超えるからである。 ${\displaystyle (1-5\varepsilon )\cdot \mathrm {OPT} (I)-4}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle (1-2\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle O(n^{1/\varepsilon ^{2}})}$ ${\displaystyle n^{1/\varepsilon ^{2}}}$ ${\displaystyle 1+1/\varepsilon ^{2}}$ ${\displaystyle \varepsilon <1/20}$ ${\displaystyle n^{400}}$

彼らはまた、オンライン版の問題に対するアルゴリズムも提示しています。オンライン設定では、漸近的な最悪ケース近似係数を1/2より良くすることはできません。しかし、平均的なケースでは良好なパフォーマンスを発揮するアルゴリズムが存在します。

JansenとSolis-Oba ^{[ 4 ]}は漸近的FPTASを提示している。これは、すべてのε >0に対して、すべての項目の合計がより大きい場合、少なくとも 個のビンを埋めるアルゴリズムである（項目の合計がそれより小さい場合、最適値はいずれにしても最大で 個になる）。実行時間は で、は逆行列を求める最良のアルゴリズムの実行時間計算量である（現在、約）。このアルゴリズムは の場合でも3/4近似よりも優れており、この場合、定数は約 程度と妥当である。 ${\displaystyle (1-\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle 13/\epsilon ^{3}\in O(1/\epsilon ^{3})}$ ${\displaystyle O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)}$ ${\displaystyle {\mathcal {T_{M}}}(n)}$ ${\displaystyle O(n^{2.38})}$ ${\displaystyle \varepsilon <1/4}$ ${\displaystyle 2^{10}n^{2}+2^{18}}$

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

[編集]

ビン被覆の重要な特殊なケースとして、アイテムのサイズが割り切れる列（因数分解とも呼ばれる）を形成することが挙げられます。割り切れるアイテムサイズの特殊なケースは、コンピュータシステムにおけるメモリ割り当てにおいて発生し、この場合、アイテムのサイズはすべて2の累乗となります。アイテムのサイズが割り切れる場合、ビン被覆のヒューリスティックアルゴリズムのいくつかは最適解を見つけます。^{[ 5 ]：第5節}

関連する問題

[編集]

公平なアイテム割り当て問題では、複数の人がそれぞれのアイテムに異なる価値を付与します。目標は、各人にアイテムが詰まった「ビン」を割り当て、各ビンの価値が少なくとも一定の定数になるようにし、できるだけ多くの人がビンを受け取れるようにすることです。この問題でも、ビンカバーリングの多くの手法が用いられます。

実装

[編集]

• Python: prtpyパッケージには、Csirik-Frenk-Labbe-Zhang アルゴリズムの実装が含まれています。

参考文献

[編集]

1. Assmann, S. F ; Johnson, D. S ; Kleitman, D. J ; Leung, JY-T (1984-12-01). 「1次元ビンパッキング問題の双対バージョンについて」. Journal of Algorithms . 5 (4): 502– 525. doi : 10.1016/0196-6774(84)90004-X . ISSN  0196-6774 .
2. Csirik, János; JBG Frenk, M. Labbé, S. Zhang (1999-01-01). 「ビンカバーリングのための2つのシンプルなアルゴリズム」 . Acta Cyber​​netica . 14 (1): 13– 25. ISSN 2676-993X . 
3. Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). 「ビンカバーリングのためのより優れた近似アルゴリズム」 .第12回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '01. ワシントンD.C., 米国: Society for Industrial and Applied Mathematics: 557–566 . ISBN 978-0-89871-490-6。
4. Jansen, Klaus; Solis-Oba, Roberto (2003). 「ビン被覆のための漸近的完全多項式時間近似スキーム」.理論計算機科学. 306 ( 1–3 ): 543–551 . doi : 10.1016/S0304-3975(03)00363-3 . MR 2000192 . 
5. 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 . 

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bin_covering_problem&oldid=1316102179"

• This page was last edited on 10 October 2025, at 13:42 (UTC).
• テキストはクリエイティブ・コモンズ 表示-継承4.0ライセンスの下で利用可能です。追加の条件が適用される場合があります。このサイトを利用することにより、利用規約とプライバシーポリシーに同意したことになります。Wikipedia®は、非営利団体であるウィキメディア財団の登録商標です。

• プライバシーポリシー
• Wikipediaについて
• 免責事項
• Wikipediaへのお問い合わせ
• 法的および安全に関する連絡先
• 行動規範
• 開発者
• 統計
• クッキーに関する声明
• モバイルビュー

• 
• 

検索

検索

目次を切り替える

ビンカバーの問題

1つの言語トピックを追加

Operations research problem of packing items into the largest number of bins

ビンカバーリング問題では、異なるサイズのアイテムを、使用されるビンの数を最大化する方法を使用して 、各ビンまたはコンテナーの合計サイズが少なくとも一定以上である有限の数のビンまたはコンテナーに詰め込む必要があります。

この問題はビンパッキング問題の双対です。ビンカバーリングでは、ビンのサイズは下から制限され、その数を最大化することが目標です。ビンパッキングでは、ビンのサイズは上から制限され、その数を最小化することが目標です。^[1]

この問題はNP困難ですが、さまざまな効率的な近似アルゴリズムがあります。

• 最適なビンの少なくとも1/2、2/3、または3/4をカバーするアルゴリズムは、それぞれ時間とともに漸近的にカウントされます。^{[1] [2]} ${\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}$
• 漸近的PTAS 、いくつかの離散分布に対して漸近的に最適な期待挙動を示す、最悪のケースの挙動が制限されたアルゴリズム、およびすべての離散分布に対して漸近的に最適な期待挙動を示す学習アルゴリズム。^[3]
• 漸近的FPTAS。^[4]

双方向ビンフィリングアルゴリズム

Csirik, Frenk, Lebbe, Zhang ^{[2] : 16–19 は}、2/3近似のための以下の単純なアルゴリズムを提示している。ビンサイズが1で、アイテム数がn個であるとする。

• 項目を最大(1)から最小( n )の順に並べます。
• ビンを最大のアイテム1、2、...、mで埋めます。ここで、mはアイテム 1、...、 mの合計が1 未満となる最大の整数です。
• このビンに、値が 1 を超えるまで、n、n -1、... という最小の項目を追加します。

任意のインスタンスIについて、最適解におけるビンの数を 、双方向充填アルゴリズムにおけるビンの数を と表記します。この場合 、 、または同等の となります 。 ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {BDF} (I)}$ ${\displaystyle \mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)}$ ${\displaystyle \mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1}$

証拠

証明には次の用語が使用されます。

• ${\displaystyle t:=\mathrm {BDF} (I)=}$アルゴリズムによって埋められたビンの数。
• ${\displaystyle B_{1},\ldots ,B_{t}:=}$アルゴリズムによって埋められたtビン。
• 初期項目-各tビンに最初に挿入されるt個の項目。
• 最終項目-各tビンに最後に挿入されるt個の項目。
• 中間項目- 最初でも最後でもないすべての項目。
• ${\displaystyle w}$ := 最大 1/2 である最終項目の数 (つまり、1/2 より大きい最終項目の数)。 ${\displaystyle t-w}$

各ビンの合計は少なくとも1ですが、最後のアイテムを除いた場合、残りの合計は1より小さくなります。最初のビン にはそれぞれ、最初のアイテム、場合によっては中間のアイテム、そして最後のアイテムが含まれます。最後のビンにはそれぞれ、最初のアイテムと最後のアイテムのみが含まれます。これは、どちらも1/2より大きく、合計が既に1より大きいためです。 ${\displaystyle B_{1},\ldots ,B_{t}}$ ${\displaystyle w}$ ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle t-w}$ ${\displaystyle B_{w+1},\ldots ,B_{t}}$

証明では2つのケースを検討します。

簡単なケースは、つまり、すべての最終アイテムが 1/2 より小さい場合です。この場合、すべての充填されたアイテムの合計は最大で 3/2 となり、残りのアイテムの合計は最大で 1 となるため、すべてのアイテムの合計は最大で となります 。一方、最適解では、すべてのビンの合計は少なくとも 1 となるため、すべてのアイテムの合計は少なくとも となります。したがって、要求どおりとなります。 ${\displaystyle w=t}$ ${\displaystyle B_{i}}$ ${\displaystyle 3t/2+1}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2+1}$

難しいケースは、つまり、いくつかの最終項目が 1/2 より大きい場合です。ここで、 の上限を、以下の和として表すことで 証明します。 ${\displaystyle w<t}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|}$

• ${\displaystyle K_{0}:=}$最初/最後のアイテムがない（中間のアイテムのみ）最適なビン。
• ${\displaystyle K_{1}:=}$ちょうど 1 つの初期/最終項目 (およびいくつかの中間項目) を含む最適なビン。
• ${\displaystyle K_{2}:=}$2 つ以上の初期/最終項目 (およびいくつかの中間項目) を含む最適なビン。

まず、およびにおける最適なビンに注目します 。各ビン内のアイテムと、少なくとも同等の価値がある におけるいくつかのアイテムとの間の一対一写像を提示します。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{t}}$

• ビン内の最初の/最後の単一のアイテムは、 の最初のアイテムにマッピングされます。これらは最大の最初のアイテムであることに注意してください。 ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$
• ビンとビンの中央のアイテムは、ビンの中央のアイテムにマッピングされます。これらのビンにはすべての中央のアイテムが含まれていることに注意してください。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{w}}$
• したがって、およびのすべての項目は、のすべての最終でない項目と、 のすべての中間項目にマッピングされます。 ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$
• 各ビンの最終項目を除く合計は 1未満です。さらに、最初の項目は1/2より大きいため、中間項目のみの合計は1/2未満です。したがって、 内の最終項目以外のすべての項目と 内の中間項目すべての合計は、最大で になります。 ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$ ${\displaystyle |K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2}$
• 各最適ビンの合計は少なくとも 1 です。したがって、 となり、 が成り立ちます。 ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2}$ ${\displaystyle 2|K_{0}|+|K_{1}|\leq w\leq t}$

ここでは、およびにおける最適なビンに焦点を当てます。 ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$

• ビンとビン内の初期/最終アイテムの総数は少なくとも 個ですが、各ビンには初期/最終アイテムがちょうど2個ずつあるため、それらの総数も 個になります。したがって、 となります。 ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$ ${\displaystyle |K_{1}|+2|K_{2}|}$ ${\displaystyle 2t}$ ${\displaystyle |K_{1}|+2|K_{2}|\leq 2t}$
• 後者の 2 つの不等式を合計すると となり、 が成り立ちます。 ${\displaystyle 2\mathrm {OPT} (I)\leq 3t}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2}$

締め付け感

BDFでは2/3係数は厳しすぎます。次の例（ただしは十分に小さい）を考えてみましょう。BDFは最初のビンを最大のアイテムで初期化し、それを最小のアイテムで埋めます。すると、残りのアイテムは3つ組のビンしか埋めることができず、結果としてすべてのビンが埋められます。しかしOPTでは、各ビンに中サイズのアイテム2つと小さなアイテム2つを含めて埋めることができます。 ${\displaystyle \epsilon >0}$ $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}}$$ ${\displaystyle 6k}$ ${\displaystyle 6k}$ ${\displaystyle 2k+1}$ ${\displaystyle 3k}$

3クラスビンフィリングアルゴリズム

Csirik、Frenk、Lebbe、Zhang ^{[2] : 19–24 は}、3/4近似を達成する別のアルゴリズムを提示している。このアルゴリズムは、アイテムを大きいものから小さいものの順に並べ、3つのクラスに分割する。

• X: サイズが少なくとも 1/2 のアイテム。
• Y: サイズが1/2未満かつ1/3以上のアイテム。
• Z: サイズが1/3未満のアイテム。

アルゴリズムは2つのフェーズで動作します。フェーズ1:

• Xの最大値、またはYの最大値2つのうち、どちらか大きい方の値で新しいビンを初期化します。どちらの場合も、初期のビンの合計は1未満であることに注意してください。
• 新しいビンに、Z から値の昇順でアイテムを入力します。
• XUY または Z のいずれかが空になるまで繰り返します。

フェーズ2:

• XUY が空の場合、単純な次適合ルールに従って、ビンを Z からのアイテムで埋めます。
• Z が空の場合、X に残っているアイテムを 2 つずつパックし、Y に残っているアイテムを 3 つずつパックします。

上記の例では、BDF のタイトネスを示し、セットは次のようになります。TCFは、すべてのビンを Y のアイテムのペアで初期化し、それらを Z のアイテムのペアで埋めるため、最適な結果を実現します。 $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots |Z|=6k\cdots \}\end{aligned}}}$$ ${\displaystyle 3k}$

任意のインスタンスIについて、最適解におけるビンの数を 、3クラス充填アルゴリズムにおける完全なビンの数 を とします。 ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {TCF} (I)}$ ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)}$

TCFの3/4係数は厳しすぎます。次の例を考えてみましょう（ただし、は十分に小さいです）。 ${\displaystyle \epsilon >0}$

$${\displaystyle {\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}}$$

TCFでは、最初のビンを最大の2つのアイテムで初期化し、そこに最小のアイテムを配置します。残りのアイテムは4つずつのグループでしかビンをカバーできないため、すべてのビンが埋められます。一方、OPTでは、各ビンに中サイズのアイテム3つと小サイズのアイテム3つずつを配置してビンを埋めることができます。 ${\displaystyle 12k}$ ${\displaystyle 12k}$ ${\displaystyle 3k+1}$ ${\displaystyle 4k}$

多項式時間近似スキーム

Csirik、Johnson、Kenyon ^[3]は漸近的PTASを提示している。これは、任意のε >0 に対して、すべての項目の合計が より大きい場合は少なくとも 個のビンを埋め、そうでない場合は少なくとも 個のビンを埋めるアルゴリズムである。実行時間は である。このアルゴリズムは、変数と制約を持つ構成線形計画の変種を解きます。このアルゴリズムは理論的にのみ興味深い。なぜなら、3/4 より優れた近似値を得るためには を取る必要があり、その場合変数の数は 個を超えるからである。 ${\displaystyle (1-5\varepsilon )\cdot \mathrm {OPT} (I)-4}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle (1-2\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle O(n^{1/\varepsilon ^{2}})}$ ${\displaystyle n^{1/\varepsilon ^{2}}}$ ${\displaystyle 1+1/\varepsilon ^{2}}$ ${\displaystyle \varepsilon <1/20}$ ${\displaystyle n^{400}}$

彼らはまた、オンライン版の問題に対するアルゴリズムも提示しています。オンライン設定では、漸近的な最悪ケース近似係数を1/2より良くすることはできません。しかし、平均的なケースでは良好なパフォーマンスを発揮するアルゴリズムが存在します。

JansenとSolis-Oba ^[4]は漸近的FPTASを提示している。これは、すべてのε >0に対して、すべての項目の合計がより大きい場合、少なくとも 個のビンを埋めるアルゴリズムである（項目の合計がそれより小さい場合、最適値はいずれにしても最大で 個になる）。実行時間は である。ここで は、逆行列を求めるための最良のアルゴリズムの実行時間計算量である（現在、約）。このアルゴリズムは の場合でも3/4近似よりも優れており、この場合、定数は約 程度と妥当である。 ${\displaystyle (1-\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle 13/\epsilon ^{3}\in O(1/\epsilon ^{3})}$ ${\displaystyle O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)}$ ${\displaystyle {\mathcal {T_{M}}}(n)}$ ${\displaystyle O(n^{2.38})}$ ${\displaystyle \varepsilon <1/4}$ ${\displaystyle 2^{10}n^{2}+2^{18}}$

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

ビン被覆の重要な特殊なケースとして、アイテムのサイズが割り切れる列（因数分解とも呼ばれる）を形成することが挙げられます。割り切れるアイテムサイズの特殊なケースは、コンピュータシステムにおけるメモリ割り当てにおいて発生し、この場合、アイテムのサイズはすべて2の累乗となります。アイテムのサイズが割り切れる場合、ビン被覆のヒューリスティックアルゴリズムのいくつかは最適解を見つけます。^{[5] : Sec.5}

関連する問題

公平なアイテム割り当て問題では、複数の人がそれぞれのアイテムに異なる価値を付与します。目標は、各人にアイテムが詰まった「ビン」を割り当て、各ビンの価値が少なくとも一定の定数になるようにし、できるだけ多くの人がビンを受け取れるようにすることです。この問題でも、ビンカバーリングの多くの手法が用いられます。

実装

• Python: prtpy パッケージには、Csirik-Frenk-Labbe-Zhang アルゴリズムの実装が含まれています。

参考文献

1. Assmann, S. F ; Johnson, D. S ; Kleitman, D. J ; Leung, JY-T (1984-12-01). 「1次元ビンパッキング問題の双対バージョンについて」. Journal of Algorithms . 5 (4): 502– 525. doi :10.1016/0196-6774(84)90004-X. ISSN  0196-6774.
2. Csirik, János; JBG Frenk, M. Labbé, S. Zhang (1999-01-01). 「ビンカバーリングのための2つのシンプルなアルゴリズム」. Acta Cyber​​netica . 14 (1): 13– 25. ISSN  2676-993X.
3. Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). 「ビンカバーリングのためのより優れた近似アルゴリズム」.第12回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '01. ワシントンD.C., 米国: Society for Industrial and Applied Mathematics: 557–566 . ISBN 978-0-89871-490-6。
4. Jansen, Klaus; Solis-Oba, Roberto (2003). 「ビン被覆のための漸近的完全多項式時間近似スキーム」.理論計算機科学. 306 ( 1–3 ): 543–551 . doi :10.1016/S0304-3975(03)00363-3. MR  2000192.
5. 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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bin_covering_problem&oldid=1316102179"

Original text

Rate this translation

Your feedback will be used to help improve Google Translate