TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1999

COGA 5-Wheel

Page Content

to Navigation

Preprints 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
Citation key Report-640-1999
Author Afrati, Foto and Bampis, Evripidis and Chekuri, Chandra and Karger, David and Kenyon, Claire and Khanna, Sanjeev and Milis, Ioannis and Queyranne, Maurice and Skutella, Martin and Stein, Cliff and Sviridenko, Maxim
Year 1999
Note in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 32-43
Institution Technische Universität Berlin, Institut für Mathematik
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 = 640, Our PTASs are also efficient. For most variants, the running time for a $(1+\epsilon)$–approximation on an instance with $n$ jobs and $m$ machines is $O(nłog 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$.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe