Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14466
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSkutella, Martin
dc.contributor.authorVerschae, Jos
dc.date.accessioned2021-12-17T10:09:05Z-
dc.date.available2021-12-17T10:09:05Z-
dc.date.issued2010
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15693-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14466-
dc.description.abstractScheduling a set of n jobs on m identical parallel machines so as to minimize the makespan or maximize the minimum machine load are two of the most important and fundamental scheduling problems studied in the literature. We consider the general online scenario where jobs are consecutively added to and/or deleted from an instance. The goal is to always maintain a (close to) optimal assignment of the current set of jobs to the m machines. This goal is essentially doomed to failure unless, upon arrival or departure of a job, we allow to reassign some other jobs. Considering that the reassignment of a job induces a cost proportional to its size, the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs.en
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherschedulingen
dc.subject.otherapproximationen
dc.subject.otheronlineen
dc.subject.otherreassignment costsen
dc.subject.otherrobustnessen
dc.subject.otherILP in constant dimensionen
dc.titleA Robust PTAS for Machine Covering and Packingen
dc.typeResearch Paperen
tub.accessrights.dnbfreeen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2010, 11en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
dc.type.versionsubmittedVersionen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-011-2010.pdf
Format: Adobe PDF | Size: 287.12 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.