Performance ratios of the Karmarkar-Karp differencing method

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

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

Abstract

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m = 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.
Original languageEnglish
Pages (from-to)19-32
Number of pages14
JournalJournal of Combinatorial Optimization
Volume13
Issue number1
DOIs
Publication statusPublished - 2007
Externally publishedYes

Fingerprint Dive into the research topics of 'Performance ratios of the Karmarkar-Karp differencing method'. Together they form a unique fingerprint.

Cite this