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

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

Worst-case Performance
Approximation algorithms
Scheduling
Polynomials
Multiprocessor Scheduling
Identical Parallel Machines
Completion Time
Polynomial-time Algorithm
Scheduling Problem
Approximation Algorithms
Open Problems
Schedule

Cite this

Michiels, W.P.A.J. ; Korst, J.H.M. ; Aarts, E.H.L. ; Leeuwen van, J. / Performance ratios of the Karmarkar-Karp differencing method. In: Journal of Combinatorial Optimization. 2007 ; Vol. 13, No. 1. pp. 19-32.
@article{7f84bb9a8b8747c69dabe79ff7aec944,
title = "Performance ratios of the Karmarkar-Karp differencing method",
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.",
author = "W.P.A.J. Michiels and J.H.M. Korst and E.H.L. Aarts and {Leeuwen van}, J.",
year = "2007",
doi = "10.1007/s10878-006-9010-z",
language = "English",
volume = "13",
pages = "19--32",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "1",

}

Performance ratios of the Karmarkar-Karp differencing method. / Michiels, W.P.A.J.; Korst, J.H.M.; Aarts, E.H.L.; Leeuwen van, J.

In: Journal of Combinatorial Optimization, Vol. 13, No. 1, 2007, p. 19-32.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Performance ratios of the Karmarkar-Karp differencing method

AU - Michiels, W.P.A.J.

AU - Korst, J.H.M.

AU - Aarts, E.H.L.

AU - Leeuwen van, J.

PY - 2007

Y1 - 2007

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

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

U2 - 10.1007/s10878-006-9010-z

DO - 10.1007/s10878-006-9010-z

M3 - Article

VL - 13

SP - 19

EP - 32

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 1

ER -