The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is $2/3$, and Chen et al.\ asked whether $2/3$ is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a $1/2$-approximation using $O(n\log(n+1)+m\log(m+1))$ arithmetic and comparison operations for $n$ items and $m$ knapsacks, and prove that no fixed ratio above $1/2$ is achievable unless $\mathsf P=\mathsf{NP}$. We also give a short proof of the classical $1/2$ guarantee of Friesen and Langston for unit profits.