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

バランス型数値分割は、多分割型数値分割の一種で、各セットに割り当てられるアイテム数に制約があります。この問題への入力は、サイズの異なるn個のアイテムのセットと、2 つの整数m、kです。出力は、アイテムをm 個のサブセットに分割したもので、各サブセットのアイテム数は最大でk 個となります。ただし、m個のサブセットのサイズの合計は、できるだけ類似している必要があります。   

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

最適なジョブスケジューリング問題の標準的な3フィールド表記では、最大和を最小化する問題は「P  | # ≤ k | C _max」と表記されることがあります。中央のフィールド「# ≤ k」は、各機械のジョブ数が最大でkである必要があることを示しています。これは、制約のないバージョンとは対照的です。制約のないバージョンは「       ${\displaystyle P\parallel C_{\max }}$「. ^{[ 3 ]}

2 方向バランス分割と呼ばれる一般的な特殊ケースは、2 つのサブセット ( m  =  2)が存在する場合です。2 つのサブセットには floor( n /2) と ceiling( n /2) 個の項目が含まれる必要があります。これは分割問題の変種です。2 つのサブセットの合計が等しくなる分割が存在するかどうかを判定するのは NP 困難です。 ^{[ 4 ]}問題 [SP12] を参照してください。合計が可能な限り等しくなるようなバランス分割を見つけることを目的としたアルゴリズムは多数あります。

• コフマン、フレデリクソン、リューカー^{[ 5 ]}は、入力がペアで割り当てられるLPTアルゴリズム の制限版（RLPTと呼ばれる）を提示している。入力が一様分布する確率変数である場合、RLPTの期待される最大合計は正確に${\displaystyle {\frac {n}{4}}+{\frac {1}{2n+2}}}$期待される仕事の差（最大合計と最小合計の差）は${\displaystyle \Theta (1/n)}$[ ^{2 ]​}
• Lueker ^{[ 6 ]}は、 LDM アルゴリズムの変種(ペアワイズ差分法 (PDM) と呼ばれる) を提示している。その期待される作業差は${\displaystyle \Theta (1/n)}$。
• Tsai ^{[ 2 ]}は制限付き最大差 (RLD) と呼ばれるアルゴリズムを発表している。その作業差は${\displaystyle O(\log n/n^{2})}$ほぼ間違いなく。
• Yakir ^{[ 7 ] は}、 m = 2の場合のLDM アルゴリズムのバランス型バリアントである BLDM を提示している。その期待される仕事の差は  ${\displaystyle n^{-\Theta (\log n)}}$。
• Mertens ^{[ 8 ]}は、バランスのとれた双方向分割のための完全ないつでも実行可能なアルゴリズムを提示している。これは、BLDM アルゴリズムと完全な Karmarkar–Karp アルゴリズムを組み合わせたものである。

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

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

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

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

カーディナリティ制約は、各部分集合に異なる制約を許容することで一般化できます。このバリアントは、^{[ 12 ]}の「未解決問題」セクションで紹介されており、 k _i分割問題と呼ばれています。He、Tan、Zhu、Yao ^{[ 16 ]}は、異なるカーディナリティ制約で最小和を最大化するHARMONIC2と呼ばれるアルゴリズムを提示しています。彼らは、その最悪ケース比が少なくともであることを証明しています。${\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個の各部分集合が独立した集合であるか、このマトロイドの基底である必要があるという一般化である。

• 基数制約は、マトロイドが一様マトロイドである場合のマトロイド制約の特殊なケースです。
• カテゴリ化されたカーディナリティ制約は、マトロイドが分割マトロイドである特殊なケースです。