direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 640-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
Authors
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein, and Maxim Sviridenko
Publication
in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 32-43
Classification
MSC:
primary: 90C27 Combinatorial optimization
secondary: 68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
Keywords
approximation algorithm, approximation scheme, scheduling
Abstract
We consider the problem of scheduling jobs with release dates on parallel machines so as to minimize average weighted completion time. While constant factor approximation algorithms for many variants have been developed in the last few years, we present the first known polynomial time approximation schemes for several of them. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our PTASs are also efficient. For most variants, the running time for a (1+ε)-approximation on an instance with n jobs and m machines is O(nlog n) for each fixed ε, and for all variants the running time's dependence on n is a fixed polynomial whose degree is independent of ε and m.
Source
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe