algorithm - 将 X 中的所有 x_i 分成 K 组 s.t. var(sum(x in k) for k 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) 近似算法(来自 Bounds on Multiprocessing Timing Anomalies ):

对数字进行排序，然后将它们分配到迄今为止最小的一组。