Computer-assisted proof of performance ratios for the Differencing Method

W.P.A.J. Michiels, E.H.L. Aarts, J.H.M. Korst, J. Leeuwen van, F.C.R. Spieksma

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)1-16
Number of pages16
JournalDiscrete Optimization
Volume9
Issue number1
DOIs
Publication statusPublished - 2012
Externally publishedYes

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