將X中的所有x_i拆分爲K個組s.t. var（K中的k的總和（x in k））最小化

Question

我有X個正數，索引爲x_i。每個x_i需要進入K個組中的一個（其中K是預先確定的）。設S_j是K_j中所有x_i的和。我需要分配所有的x_i，使所有S_j的方差最小化。什麼算法完成這個？我確定有一些算法可以解決這樣的問題，但我不知道。

謝謝

Answer 1

這是一個packing problem。鑑於這類問題大多數是NP-hard，您不可能找到有效的最優算法。

Multiprocessor scheduling它試圖最小化最大組的大小有一個簡單的4/3 - 1 /（3K）近似alrogithm（從 Bounds on Multiprocessing Timing Anomalies）：

排序的數量，然後將它們分配到最小的組至今。