46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) Pittsburgh, Pennsylvania, USA October 23-October 25 ISBN: 0-7695-2468-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.21
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. We obtain 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 (3/2 and 2, respectively); (ii) better-than two approximation guarantees for scheduling under the Lp norm for all 1 < p < \infty, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constantfactor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al. and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resourcedependent processing times studied by Grigoriev et al.
Citation:
V.S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan, "Approximation Algorithms for Scheduling on Multiple Machines," focs, pp.254-263, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||