A note on the average-case behavior of a simple differencing method for partitioning

Given n positive values x₁, x₂,…, x_n, we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. Karp and Karmarkar have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributions, a difference of O(n^−alogn), for some α > 0, with probability approaching 1 as n → ∞. Their work left open the question of how two simple and more natural implementations of the algorithm behaved. In this paper, under the assumption that the input values are uniformly distributed, we show that one of these algorithms is not nearly so effective, confirming empirical observations of Karp.