A PTAS for minimizing the total weighted completion time on identical parallel machines

dc.contributor.authorSkutella, Martin
dc.contributor.authorJ. Woeginger, Gerhard
dc.date.accessioned2021-12-17T10:17:01Z
dc.date.available2021-12-17T10:17:01Z
dc.date.issued1999
dc.description.abstractWe 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 ((1+ 2}))/2-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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15943
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14716
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmen
dc.subject.otherapproximation schemeen
dc.subject.otherschedulingen
dc.titleA PTAS for minimizing the total weighted completion time on identical parallel machinesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1999, 628en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200068Q25 Analysis of algorithms and problem complexityen
tub.subject.msc200090B35 Scheduling theory, deterministicen
tub.subject.msc200068M20 Performance evaluation; queueing; schedulingen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-628-1999.pdf
Size:
245.18 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-628-1999.ps.gz
Size:
89.69 KB
Format:
Unknown data format
Description:
Collections