バランスのとれた数の分割

バランスド・ナンバー・パーティショニングは、各集合に割り当てられるアイテムの数に制約があるマルチウェイ・ナンバー・パーティショニングの変形です。この問題への入力は、サイズの異なるn個のアイテムの集合と、2つの整数 m、  kです。出力は、アイテムをm 個のサブセットに分割したもので、各サブセットのアイテム数は最大で k 個となります。この制約のもと、 m個のサブセットのサイズの合計は可能な限り近似していることが求められます。

応用例としては、各マシンが最大k個のジョブを保持できるジョブキューを持つ同一マシンスケジューリングが挙げられる。[1]この問題は、 VLSIチップの製造や、フレキシブル生産システムにおけるマシンへのツールの割り当てにも応用できる。[2]

最適ジョブスケジューリング問題における標準的な3フィールド表記法では、最大和を最小化する問題は「P  |  # ≤ k  |  C max」と表記されることがあります。中間のフィールド「# ≤ k」は、各マシンのジョブ数が最大でkであるべきであることを示します。これは、「 」と表記される制約なしバージョンとは対照的です。[3] P ∥ C max {\displaystyle P\parallel C_{\max }}

双方向バランスパーティショニング

2元均衡分割と呼ばれる一般的な特殊なケースは、2つの部分集合（m  = 2）が存在する場合です。2つの部分集合には、floor( n /2)個とceiling( n /2)個の項目が含まれます。これは分割問題の一種です。2つの部分集合の合計が等しい分割が存在するかどうかを判断することはNP困難です。[4]の問題[SP12]を参照してください。合計が可能な限り等しくなる均衡分割を見つけることを目的とするアルゴリズムは数多く存在します。

  • Coffman、Frederickson、Lueker [5]は、 LPTアルゴリズム の制限版（RLPTと呼ばれる）を提示している。RLPTでは、入力はペアで割り当てられる。入力が一様分布の確率変数である場合、RLPTの最大和の期待値はちょうど である。期待される作業差（最大和と最小和の差）は である。[2] n 4 + 1 2 n + 2 {\displaystyle {\frac {n}{4}}+{\frac {1}{2n+2}}} Θ ( 1 / n ) {\displaystyle \Theta (1/n)}
  • Lueker [6]はLDMアルゴリズムの変種（ペアワイズ差分法（PDM）と呼ばれる）を提示している。その期待作業差は である。 Θ ( 1 / n ) {\displaystyle \Theta (1/n)}
  • Tsai [2]は、 Restricted Largest Difference (RLD)と呼ばれるアルゴリズムを提示している。その作業差はほぼ確実に である。 O ( log ⁡ n / n 2 ) {\displaystyle O(\log n/n^{2})}
  • Yakir [7]は、 m = 2の場合のLDMアルゴリズムのバランスの取れた変種で あるBLDMを提示している。その期待作業差は である。 n − Θ ( log ⁡ n ) {\displaystyle n^{-\Theta (\log n)}}
  • Mertens [8]は、バランス型2元分割のための完全ないつでも実行可能なアルゴリズムを提示している。これは、BLDMアルゴリズムと完全なKarmarkar-Karpアルゴリズムを組み合わせたものである。

バランスのとれた三重項分割

3分割と呼ばれるもう一つの特殊なケースは、各部分集合のアイテム数が最大3（k  = 3）となる場合です。このような、和が等しい分割が存在するかどうかを判断することは、まさに3分割問題であり、これは強いNP困難であることが知られています。和が可能な限り等しくなる分割を見つけることを目的とした近似アルゴリズムが存在します。

  • KellererとWoeginger [9]は、 LPTアルゴリズムをトリプレット分割（最大3* m個のアイテムがあり、各サブセットに含まれるアイテムが最大3個まで）に適用した。彼らのアルゴリズムは修正LPTまたはMLPTと呼ばれる。このアルゴリズムは、アイテムを大きいものから小さいものの順に並べ、各アイテムを3個未満のアイテムを含むビンの中で合計が最小のビンに順番に配置する。彼らは、MLPTアルゴリズムが最大合計の最小値、つまり制約なしの問題でLPTが達成する近似比と同じ値を達成することを示している。MLPTの境界は厳密である。 4 m − 1 3 m {\displaystyle {\frac {4m-1}{3m}}}
  • Chen、He、Lin [10]は、同じ問題に対してMLPTが少なくとも最大最小和を達成することを示し、これは制約のない問題に対してLPTが達成する比率と同じである。 3 m − 1 4 m − 2 {\displaystyle {\frac {3m-1}{4m-2}}}
  • ケラーとコトフ[11]は、（ちょうど3* m個のアイテムを持つ場合の）異なるアルゴリズムを提示しており、これは最大合計の最小値以下を達成する。 7 / 6 {\displaystyle 7/6}

より大きなカーディナリティによるバランスのとれたパーティショニング

より一般的なケースはk分割と呼ばれ、[12]各サブセット内のアイテムの数が最大でkになる場合です。ここでkは任意の正の整数です。

  • Babel、Kellerer、およびKotov [12]は、 k × m個のアイテム（ kは整数 ）が存在し、各m個の集合にはそれぞれk個のアイテムが含まれるという変種を研究した。彼らは、最小最大和を 近似するためのいくつかのヒューリスティックアルゴリズムを提示している。
    • 折りたたみアルゴリズム: m  = 2 の場合に最適であり、一般に近似比が厳密です。 2 − 1 m {\displaystyle 2-{\frac {1}{m}}}
    • 交換アルゴリズム：厳密な近似比。多項式時間で実行されるかどうかは不明です。 2 − 2 m + 1 {\displaystyle 2-{\frac {2}{m+1}}}
    • プライマルデュアルアルゴリズム（LPTとMultiFitの組み合わせ）：近似比は最大。mが十分に大きい場合、 k  = 4のときにタイトである。正確な下限は である。[12] ：Thm.11  4 / 3 {\displaystyle 4/3} 4 m 3 m + 1 {\displaystyle {\frac {4m}{3m+1}}}
    • また、修正LPTの近似比は であるという予想もある。現在、この予想はk  = 3の場合にのみ成り立つことが知られている[9]。k > 3の場合 、その近似比は最大で2であることが知られている[3]。 4 m − 1 3 m {\displaystyle {\frac {4m-1}{3m}}}
  • Michiels、Korst、Aarts、van Leeuwen [13]および Spieksma [14]は、 m個のセットそれぞれがceiling( n / m ) または floor( n / m ) 個の項目のいずれか (つまりk  = ceiling( n / m )) を含まなければならない変形を研究している。彼らは、Balanced-LDM (BLDM) をm =2 から一般的なmに拡張している。一般化されたアルゴリズムは、時間 で実行される。彼らは、最小最大和の近似比がk  = 3 の場合は正確に 4/3、k  = 4 の場合は 19/12、k = 5 の場合は 103/60、 k = 6 の場合は 643/360  、k = 7 の場合は 4603/2520 であることを証明している。この比率は、混合整数線形計画法 を解くことで求められた。一般に (任意のkに対して)、近似比は少なくともで最大 である。k >7の場合、正確な結果は不明ですが、下限と上限の差は0.3%未満です。パラメータがサブセット数（m）の場合、近似率はちょうど となります。 O ( n log ⁡ n ) {\displaystyle O(n\log n)} 2 − ∑ j = 0 k − 1 j ! k ! {\displaystyle 2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}} 2 − 1 k − 1 {\displaystyle 2-{\frac {1}{k-1}}} 2 − 1 m {\displaystyle 2-{\frac {1}{m}}}
  • Zhang、Mouratidis、およびPang [1]は、入力が均一に分布している場合と分布が偏っている場合の両方において、BLDMは作業差（最高値と最低値の合計の差）の大きいパーティションを生成する可能性があることを示しています。彼らは2つの代替的なヒューリスティックを提案しています。LRMは、分布が均一な場合、作業差をBLDMの1/3に削減します。Meldは、分布が偏っている場合、作業差を削減します。BLDM 、LRM、およびMeldを組み合わせたハイブリッドアルゴリズムは、さまざまなデータ分布に動的に適応します。
  • kが固定されている場合、ホッホバウムとシュモイズ[15]のPTASをバランス分割に使用できます。[14] kが入力の一部である場合、現在のところPTASは知られていません。 [14]
  • Dell'AmicoとMartello [3]は、すべてのセットのアイテム数が最大でkであるときに、最大和を最小化する問題を研究しています。彼らは、このバリアントの線形計画緩和が、制約のないバリアントのLP緩和と同じ最適値を持つことを示しています。式（x iは大きいものから小さいものに順序付けられた入力）は、最適な最大和の下限であり、その最悪ケースの比は両方のバリアントで1/2です。改善された式は、制約のないバリアントで最悪のケースの比が2/3、制約のあるバリアントで1/2です。修正されたリストスケジューリングの近似比は、制約のないバリアントでは1/2ですが、制約のあるバリアントでは0です（任意に悪い場合があります）。修正LPTアルゴリズムの近似比は最大2である。また、 [12]の下限は最悪のケースの性能比が3/4と厳しく、PDアルゴリズムの性能比は4/3（mが十分に大きい場合）と厳しいことも示している。 max ( ( ∑ x i ) / m , x 1 ) {\displaystyle \max((\sum x_{i})/m,x_{1})} max ( ( ∑ x i ) / m , x 1 , x k + x m + 1 ) {\displaystyle \max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})}
  • He、Tan、Zhu、およびYao [16]は、最小の合計を最大化する問題を考察しています。彼らは、FOLDINGアルゴリズムが厳密な近似比 を持つことを示しました。彼らは、最悪ケースの比が少なくとも である新しいアルゴリズムHARMONIC1 を提示しました。これらのアルゴリズムは両方とも順序論的です。つまり、項目をそれらの正確な値ではなく、それらの間の順序のみに基づいて分割します。彼らは、最小の合計を最大化するために、どの順序論的アルゴリズムでも比が最大であることを証明しています。これは、HARMONIC1 が漸近的に最適 であることを示しています。任意の固定kに対して、どの順序論的アルゴリズムでも比は最大で方程式の最小の根 になります。kが無限大に近づくと、この上限は0に近づきます。 max ( 2 k , 1 m ) {\displaystyle \max \left({\frac {2}{k}},{\frac {1}{m}}\right)} max ( 1 k , 1 ⌈ ∑ i = 1 m 1 i ⌉ + 1 ) {\displaystyle \max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)} O ( 1 / ln ⁡ m ) {\displaystyle O(1/\ln {m})} ∑ i = 1 m ⌊ ⌊ k + i − 1 i ⌋ x ⌋ = k {\displaystyle \sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k}

バランスのとれた問題と制約のない問題の関係

バランスのとれた分割問題と標準的な（制約のない）分割問題の近似の間には、いくつかの一般的な関係があります。

  • Babel、Kellerer、Kotov [12]は、制約なしの最適解と制約付き最適解の比は最大でも であり、タイトであることを証明している。 2 − 2 m {\displaystyle 2-{\frac {2}{m}}}
  • ケラーとコトフ[11]は、容量kと近似比r（最小最大和）のバランスの取れた分割に関するあらゆるヒューリスティックを用いて、近似比rの制約のない分割に関するヒューリスティックを得ることができることを証明した。特に、彼らのトリプレット分割（k  = 3）に関する近似アルゴリズムは、近似比rの制約のない分割に関するヒューリスティックを得るために使用できる。 max ( r , k + 2 k + 1 − 1 m ( k + 1 ) ) {\displaystyle \max \left(r,{\frac {k+2}{k+1}}-{\frac {1}{m(k+1)}}\right)} 7 / 6 {\displaystyle 7/6} max ( 7 6 , 5 4 − 1 4 m ) {\displaystyle \max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)}

異なるカーディナリティ制約

基数制約は、各部分集合に異なる制約を課すことで一般化できます。この変種は、[12]の「未解決問題」のセクションで導入されており、彼らはk i分割問題を と呼んでいます。He、Tan、Zhu、Yao [16]は、異なる基数制約の下で最小和を最大化するHARMONIC2と呼ばれるアルゴリズムを提示しています。彼らは、その最悪ケースの比が少なくとも であることを証明しています。 max ( 1 k m , k 1 k m 1 ⌈ ∑ i = 1 m 1 i ⌉ + 1 ) {\displaystyle \max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)}

分類されたカーディナリティ制約

カーディナリティ制約の別の一般化は以下のとおりです。入力アイテムはk 個のカテゴリに分割されます。各カテゴリhには、容量制約k hが存在します。m個のサブセットのそれぞれには、カテゴリhから最大k h個のアイテムを含めることができます。言い換えれば、すべてのm個のサブセットは、特定の分割マトロイドの独立集合である必要があります。この問題の特殊なケースが2つ研究されています。

カーネルパーティショニング

カーネル均衡分割問題において、m個の事前指定された要素はカーネルであり、m個の部分集合のそれぞれには1つのカーネル（および無制限の数の非カーネル）が含まれなければならない。ここでは、2つのカテゴリが存在する。1つは容量1のカーネルカテゴリ、もう1つは容量無制限の非カーネルカテゴリである。

  • Chen、He、Yao [17]は、k  = 3の場合でも問題がNP困難であることを証明しています（ k = 2の場合には、最大重みマッチングを 見つけることで効率的に解くことができます）。次に、 Kernel-LPT （KLPT）と呼ばれるアルゴリズムを提示しています。これは、各サブセットにカーネルを割り当て、修正されたLPTアルゴリズムを実行します（各アイテムを、 k個未満のアイテムを持つサブセットの中で合計が最小のサブセットに配置します）。彼らは、k = 3の場合、KLPTは最小最大和の 近似比を持つことを証明しています。[17] : 3 ただし、Chen、He、Lin [10] : 2 は、その厳密な近似比は最小最大和[説明が必要]および最大最小和に対してであると主張しています。 4 m − 1 3 m {\displaystyle {\frac {4m-1}{3m}}} 3 m − 1 2 m {\displaystyle {\frac {3m-1}{2m}}} 2 m − 1 3 m − 2 {\displaystyle {\frac {2m-1}{3m-2}}}

カテゴリごとに1つのパーティション

この問題の別のバリエーションでは、サイズmのk個のカテゴリがあり、各サブセットには各カテゴリから正確に 1 つのアイテムが含まれます。つまり、 各カテゴリ hについてk h = 1 となります。

  • WuとYao [18] [19]は、LPTアルゴリズムの変種である階層型LPTアルゴリズムを提示した。彼らは、その近似比が最大和を最小化するためのものであり、一般的な場合には最小和を最大化するためのものであり、また、いくつかの特殊なケースでは、一般のkに対しては近似比が、k  = 3に対しては近似比が改善できることを証明した。 2 − 1 m {\displaystyle 2-{\frac {1}{m}}} 1 m {\displaystyle {\frac {1}{m}}} m 2 m − 1 {\displaystyle {\frac {m}{2m-1}}} m − 1 2 m − 3 {\displaystyle {\frac {m-1}{2m-3}}}
  • LiとLi [20]は、同じ問題に対して異なるアルゴリズムを提示した。最大和を最小化するアルゴリズムとして、定数kに対するEPTASと定数mに対するFPTASを提示した。最小和を最大化するアルゴリズムとして、一般的なケースでは1/( k − 1)近似アルゴリズムを、定数k に対するEPTASを提示した。彼らはまた、より一般的な目的、すなわち和のベクトルのlpノルムを最小化するアルゴリズムも研究した。彼らは、階層化LPTアルゴリズムがすべてのノルムに対して2近似アルゴリズムであることを証明した。
  • Dell'Olmo、Hansen、Pallottino、およびStorchi [21]は、この問題について32の異なる目的関数を研究している。max、min、sum、diffの4つの演算子のそれぞれについて、1つの演算子を各サブセット内のk個の項目に適用し、次に1つの演算子を異なるサブセットのm個の結果に適用することができる。これらの16の目的はそれぞれ最大化または最小化することができ、合計32個ある。彼らは、これらの問題のうち21の問題は線形時間で解くことができること、7つの問題はより複雑ではあるものの依然として多項式時間アルゴリズムを必要とすること、3つの問題（(min, sum)の最大化、(max, sum)の最小化、および(diff, sum)の最小化）はNP困難であることを示している。彼らは(diff, diff)の最小化の状態を未解決のままにしている。

参照

マトロイド制約数分割は、固定マトロイドがパラメータとして与えられ、m個のサブセットのそれぞれがこのマトロイドの独立セットまたは基底となる一般化です。

参考文献

  1. ^ ab Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). 「バランスの取れた多方向数値分割のためのヒューリスティックアルゴリズム」第22回人工知能国際合同会議。
  2. ^ abc Tsai, Li-Hui (1992-02-01). 「バランスの取れた並列プロセッサスケジューリングアルゴリズムの漸近解析」 . SIAM Journal on Computing . 21 (1): 59– 64. doi :10.1137/0221007. ISSN  0097-5397.
  3. ^ abc Dell'Amico, Mauro; Martello, Silvano (2001). 「カーディナリティ制約付きP∥Cmax問題の境界」 . Journal of Scheduling . 4 (3): 123– 138. doi :10.1002/jos.68. hdl : 11380/15976 . ISSN  1099-1425.
  4. ^ ゲイリー、マイケル、ジョンソン、デイヴィッド (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 pp. 96–105. ISBN 978-0-7167-1045-5。
  5. ^ Coffman, EG; Frederickson, GN; Lueker, GS (1984-05-01). 「2つのプロセッサにおける独立タスクの最大優先シーケンスの期待メイクスパンに関する考察」 .オペレーションズ・リサーチ数学. 9 (2): 260– 266. doi :10.1287/moor.9.2.260. ISSN  0364-765X.
  6. ^ Lueker, George S (1987-12-01). 「パーティショニングにおける単純差分法の平均ケース挙動に関する考察」 .オペレーションズ・リサーチ・レターズ. 6 (6): 285– 287. doi :10.1016/0167-6377(87)90044-7. ISSN  0167-6377.
  7. ^ Yakir, Benjamin (1996-02-01). 「パーティショニングのための差分アルゴリズムLDM：KarmarkarとKarpの予想の証明」 .オペレーションズ・リサーチ数学. 21 (1): 85– 99. doi :10.1287/moor.21.1.85. ISSN  0364-765X.
  8. ^ Mertens, Stephan (1999-03-11). 「バランスのとれた数値分割のための完全ないつでもアルゴリズム」. arXiv : cs/9903011 .
  9. ^ ab Kellerer, Hans; Woeginger, Gerhard (1993-09-07). 「3分割の厳密な境界」.離散応用数学. 45 (3): 249– 259. doi : 10.1016/0166-218X(93)90013-E . ISSN  0166-218X.
  10. ^ ab Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). 「最小負荷を最大化する3分割問題」 . Journal of Combinatorial Optimization . 6 (1): 67– 80. doi :10.1023/A:1013370208101. ISSN  1573-2886. S2CID  9053629.
  11. ^ ab Kellerer, Hans; Kotov, Vladimir (1999-02-01). 「3分割のための7/6近似アルゴリズムとマルチプロセッサスケジューリングへの応用」 . INFOR: 情報システムとオペレーションズリサーチ. 37 (1): 48– 56. doi :10.1080/03155986.1999.11732368. ISSN  0315-5986.
  12. ^ abcdef Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). 「k-分割問題」 .オペレーションズ・リサーチの数学的手法. 47 (1): 59– 82. doi :10.1007/BF01193837. ISSN  1432-5217. S2CID  5594197.
  13. ^ ウィル・マイケルズ;ヤン・コルスト。アーツ、エミール。 van Leeuwen、Jan (2003)、平衡数分割問題に適用された差分法のパフォーマンス比、コンピュータ サイエンスの講義ノート、vol. 2607、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp.  583–595、doi :10.1007/3-540-36494-3_51、ISBN 978-3-540-00623-7、 2021年10月15日閲覧
  14. ^ abc マイケルズ、W.;アーツ、E.コースト、J.ヴァン・レーウェン、J.スピースマ、FCR (2012-02-01)。 「差分法のパフォーマンス比のコンピュータ支援証明」。離散最適化。9 (1): 1–16 .土井: 10.1016/j.disopt.2011.10.001。ISSN  1572-5286。
  15. ^ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). 「スケジューリング問題における双対近似アルゴリズムの使用：理論と実践的結果」Journal of the ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN  0004-5411. S2CID  9739129.
  16. ^ ab He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). 「最小負荷を最大化するκ-分割問題」. Computers & Mathematics with Applications . 46 (10): 1671– 1681. doi : 10.1016/S0898-1221(03)90201-X . ISSN  0898-1221.
  17. ^ ab Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). 「カーネルを含む3分割：計算量とヒューリスティック」 . Computing . 57 (3): 255– 271. doi :10.1007/bf02247409. ISSN  0010-485X. S2CID  21935917.
  18. ^ Wu, Biao; Yao, Enyue (2007-04-20). 「分割マトロイド制約を伴うm-分割問題」.理論計算機科学. 374 (1): 41– 48. doi :10.1016/j.tcs.2006.11.016. ISSN  0304-3975.
  19. ^ Wu, Biao; Yao, En-yu (2008-03-01). 「分割マトロイド制約を伴うm分割問題に対する下限値と修正LPTアルゴリズム」 .中国大学応用数学誌. 23 (1): 1– 8. doi :10.1007/s11766-008-0101-8. ISSN  1993-0445. S2CID  16565038.
  20. ^ Li, Weidong; Li, Jianping (2013-04-06). 「分割マトロイド制約を伴う $$m$$ 分割問題に対する近似アルゴリズム」 . Optimization Letters . 8 (3): 1093– 1099. doi :10.1007/s11590-013-0637-2. ISSN  1862-4472. S2CID  3385030.
  21. ^ デッロルモ、パオロ;ハンセン、ピエール。パロッティノ、ステファノ。ストルキ、ジョバンニ (2005-09-01)。 「均一な k パーティションの問題について」。離散応用数学。150 (1): 121–139。土井:10.1016/j.dam.2005.02.013。ISSN  0166-218X。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Balanced_number_partitioning&oldid=1317306788"