Performance ratios for the differencing method applied to the balanced number partitioning problem

W.P.A.J. Michiels, J.H.M. Korst, E.H.L. Aarts, J. Leeuwen van

Research output: Other contribution

9 Citations (Scopus)

Abstract

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 prove that the performance ratios of the Differencing Method of Karmarkar and Karp for k = 3,4,5, and 6 are precisely 4/3, 19/12, 103/60, and 643/360, respectively, by means of a novel approach in which the ratios are explicitly calculated using mixed integer linear programming. Moreover, we show that for k = 7 the performance ratio lies between 2/3 - 2/k and 2/3 - 1/(k/3 - 1). For the case that m is given instead of k, we prove a performance ratio of precisely 2 - 1/m. The results settle the problem of determining theworst-case performance of the Differencing Method.
Original languageEnglish
PublisherSpringer
Number of pages13
Place of PublicationBerlin
ISBN (Print)3-540-00623-0
DOIs
Publication statusPublished - 2003
Externally publishedYes

Fingerprint Dive into the research topics of 'Performance ratios for the differencing method applied to the balanced number partitioning problem'. Together they form a unique fingerprint.

Cite this