我们研究一个基本的负载均衡问题：$N$ 个正整数大小的项目，总大小为 $W$，需要分配到 $B$ 个箱子，项目可以被划分为整数大小的碎片。每个箱子的负载必须是 $\lfloor W/B \rfloor$ 或 $\lceil W/B \rceil$，保证任意两箱负载差不超过 1。目标是最小化任意箱子中不同项目碎片的最大数量。该问题是 NP 难的，已有 $O(N\log N + B)$ 时间的 $(\mathrm{OPT}+1)$ 近似算法 [Kobert et al., 2014]，并被多种系统用于系统发育树重建。本文聚焦于 $B\ge N$ 的情形，即箱子不少于项目，这在现代并行/分布式系统以及迭代重平衡算法中普遍出现，箱子对应机器或核心，项目对应计算任务。我们提出一个仅需 $O(N)$ 时间、使用 $O(N)$ 空间的算法，能够在该设置下得到最优分配。我们证明最优解必然可以使每个箱子最多包含两个碎片，并给出恰好每箱一个碎片即可的判定条件。该结果严格优于 Kobert 等人的 $(\mathrm{OPT}+1)$ 近似，在多箱情形下实现精确求解，并结合原算法得到一个对任意 $B$ 的强多项式时间 $(\mathrm{OPT}+1)$ 近似，去除了对 $B$ 的依赖。
点评：该线性时间算法在实际大规模并行调度中具有直接的应用价值，尤其在任务数远小于核心数时能够保证最小碎片化开销。