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

Given n positive values \(x_ 1,x_ 2,...,x_ n\), we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. \textit{N. Karmarkar} and \textit{R. M. Karp} [``The differencing method of set partitioning'', Report No.UCB/CSD 82/113, Computer Science Division (EECS), Unif. of California, Berkeley (1982)] have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributions, a difference of \(O(n^{-\alpha \log n})\), for some \(\alpha >0\), with probability approaching 1 as \(n\to \infty\). 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.