### Abstract

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%.

Original language | English |
---|---|

Pages (from-to) | 1-16 |

Number of pages | 16 |

Journal | Discrete Optimization |

Volume | 9 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2012 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'Computer-assisted proof of performance ratios for the Differencing Method'. Together they form a unique fingerprint.

## Cite this

Michiels, W. P. A. J., Aarts, E. H. L., Korst, J. H. M., Leeuwen van, J., & Spieksma, F. C. R. (2012). Computer-assisted proof of performance ratios for the Differencing Method.

*Discrete Optimization*,*9*(1), 1-16. https://doi.org/10.1016/j.disopt.2011.10.001