Computer-assisted proof of performance ratios for the Differencing Method

We consider the problem of partitioning a set of nn numbers into mm subsets of cardinality k=⌈n/m⌉k=⌈n/m⌉ or ⌊n/m⌋⌊n/m⌋, such that the maximum subset sum is minimal. We show that the performance ratio of the Differencing Method of Karmarkar and Karp for solving this problem is at least 2−∑i=0k−1i!k! for any fixed kk. We also build a mixed integer linear programming model (milp) whose solution yields the performance ratio for any given kk. For k≤7k≤7 these milp-instances can be solved with an exact milp-solver. This results in a computer-assisted proof of the tightness of the aforementioned lower bound for k≤7k≤7. For k>7k>7 we prove that 2−1k−1 is an upper bound on the performance ratio, thereby leaving a gap with the lower bound of Θ(k−3)Θ(k−3), which is less than 0.4%.