loading...
Approximation Algorithms for Scheduling on Multiple Machines
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.2146th Annual IEEE Symposium on Foundat ...
 This Article 
 
PURCHASE ARTICLE: $0
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.