A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
Martin Skutella, Gerhard J. Woeginger
Source record
Source: Crossref
Published: Feb 1, 2000
DOI: 10.1287/moor.25.1.63.15212
Open original source ↗Source abstract
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 [Formula: see text]-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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.