Record Details

Precedence constrained scheduling in (2-7/3p+1) . optimal

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Precedence constrained scheduling in (2-7/3p+1) . optimal
 
Creator GANGAL, D
RANADE, A
 
Subject processors
precedence constrained scheduling
approximation algorithm
deadline
 
Description We present a polynomial time approximation algorithm for unit time precedence constrained scheduling. Our algorithm guarantees schedules which are at most (2 - 7/3p +1) factor as long as the optimal, where p > 3 is the number of processors. This improves upon a long standing bound of (2 - 2/p) due to Coffman and Graham. (C) 2008
 
Publisher ACADEMIC PRESS INC ELSEVIER SCIENCE
 
Date 2011-07-12T16:40:43Z
2011-12-26T12:48:59Z
2011-12-27T05:34:33Z
2011-07-12T16:40:43Z
2011-12-26T12:48:59Z
2011-12-27T05:34:33Z
2008
 
Type Article
 
Identifier JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 74(7), 1139-1146
0022-0000
http://dx.doi.org/10.1016/j.jcss.2008.04.001
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3384
http://hdl.handle.net/10054/3384
 
Language en