The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp

The algorithm LDM (largest differencing method) divides a list of n random items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items are i.i.d. and uniform then the rate of convergence of this parameter to zero is n^{−Θ(log n)}. An algorithm for balanced partitioning is constructed, with the same rate of convergence to zero.