Computer-assisted proof of performance ratios for the Differencing Method

作者：Michiels W^*; Aarts E; Korst J; van Leeuwen J; Spieksma F C R

来源：Discrete Optimization, 2012, 9(1): 1-16.

DOI：10.1016/j.disopt.2011.10.001

• Differencing Method
• Balanced number partitioning
• Worst-case performance
• Computer-assisted proof
• Mixed integer linear programming
• Exact LP solver

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 show that the performance ratio of the Differencing Method of Karmarkar and Karp for solving this problem is at least 2 - Sigma(k-01)(i=0) ll/kl 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 2 - 1/k-1 is an upper bound on the performance ratio, thereby leaving a gap with the lower bound of Theta(k-3), which is less than 0.4%.

• 出版日期2012-2
• 单位KU Leuven