@article {17549,
title = {A unified approach to scheduling on unrelated parallel machines},
journal = {J. ACM},
volume = {56},
year = {2009},
month = {2009/08//},
pages = {28:1{\textendash}28:31 - 28:1{\textendash}28:31},
abstract = {We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lp norm of the vector of machine-loads, for all 1 < p < $\infty$; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys \& Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].},
keywords = {Approximation algorithms, Randomized rounding, scheduling under multiple criteria},
isbn = {0004-5411},
doi = {10.1145/1552285.1552289},
url = {http://doi.acm.org/10.1145/1552285.1552289},
author = {Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}