research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleApproximation schemes for scheduling and covering on unrelated machines
Bibtex cite IDRACTI-RU1-2006-79
Journal Theoretical Computer Science (TCS)
Year published 2006
Month August
Volume 359
Number 1-3
Pages 400-417
ISSN 0304-3975
Keywords Randomized rounding; Multi-objective scheduling; Covering; Approximation schemes; Derandomization
We examine the problem of assigning n independent jobs to m unrelated parallel machines, so that each job is processed without interruption on one of the machines, and at any time, every machine processes at most one job. We focus on the case where m is a fixed constant, and present a new rounding approach that yields approximation schemes for multi-objective minimum makespan scheduling with a fixed number of linear cost constraints. The same approach gives approximation schemes for covering problems like maximizing the minimum load on any machine, and for assigning specific or equal loads to the machines.
Efraimidis, Pavlos
Spirakis, Paul
fulltext.pdf (main file)
Publication ID343