direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

A PTAS for minimizing the total weighted completion time on identical parallel machines
Zitatschlüssel Report-628-1999
Autor Martin Skutella and Gerhard J. Woeginger
Jahr 1999
Nummer 628
Notiz Mathematics of Operations Research, 25(1), 63-75, 2000. An extended abstract appeared in the proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 400–407.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the problem of scheduling a set of $n$ jobs on $m$ identical parallel machines so as to minimize the weighted sum of job completion times. This problem is NP-hard in the strong sense. The best approximation result known so far was a $\frac12(1+\sqrt2)$-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, our result constitutes the first known approximation scheme for a strongly NP-hard scheduling problem with minsum objective.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag