We study a fundamental load‑balancing problem: $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, and items may be split into integer‑size fragments. Each bin’s load must be either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, guaranteeing that any two bins differ by at most one unit. The objective is to minimize the maximum number of distinct item fragments placed in any single bin. The problem is NP‑hard; a $O(N\log N + B)$‑time $(\mathrm{OPT}+1)$‑approximation algorithm [Kobert et al., 2014] exists and is used in several phylogenetic reconstruction codes. This work focuses on the case $B\ge N$, i.e., there are at least as many bins as items, a setting common in modern parallel and distributed systems and in iterative algorithms that rebalance work each step. Here bins correspond to machines or cores and items to computational jobs. We present a remarkably simple $O(N)$‑time algorithm that computes an optimal assignment using $O(N)$ space. We prove that an optimum always exists where each bin receives at most two fragments and we characterize when a single fragment per bin suffices. This result strictly improves the $(\mathrm{OPT}+1)$‑approximation of Kobert et al. in the many‑bins regime and, together with their algorithm, yields a strongly polynomial‑time $(\mathrm{OPT}+1)$‑approximation for the general case, eliminating dependence on $B$.
Review: The linear‑time exact algorithm offers immediate practical benefits for large‑scale parallel scheduling, especially when the number of tasks is far smaller than the number of cores, ensuring minimal fragmentation overhead.