Computer-assisted proof of performance ratios for the Differencing Method

We consider the problem of partitioning a set of n numbers into m subsets of cardinality [formula omitted], 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 [formula omitted] for any fixed k. We also build a mixed integer linear programming model (milp) whose solution yields the performance ratio for any given k. For k=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=7. For k>7 we prove that [formula omitted] is an upper bound on the performance ratio, thereby leaving a gap with the lower bound of T(k-3), which is less than 0.4%.