loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
Pittsburgh, Pennsylvania, USA
October 23-October 25
ISBN: 0-7695-2468-0
V.S. Anil Kumar, Virginia Tech
Madhav V. Marathe, Virginia Tech
Srinivasan Parthasarathy, University of Maryland
Aravind Srinivasan, University of Maryland

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.