Performance ratios for the differencing method applied to the balanced number partitioning problem

We consider the problem of partitioning a set of n numbers into m subsets of cardinality k = ¿n/m¿ or ¿n/m¿, such that the maximum subset sum is minimal. We prove that the performance ratios of the Differencing Method of Karmarkar and Karp for k = 3,4,5, and 6 are precisely 4/3, 19/12, 103/60, and 643/360, respectively, by means of a novel approach in which the ratios are explicitly calculated using mixed integer linear programming. Moreover, we show that for k = 7 the performance ratio lies between 2/3 - 2/k and 2/3 - 1/(k/3 - 1). For the case that m is given instead of k, we prove a performance ratio of precisely 2 - 1/m. The results settle the problem of determining theworst-case performance of the Differencing Method.