Record Details

Scheduling loosely connected task graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Scheduling loosely connected task graphs
 
Creator RANADE, ABHIRAM
 
Subject polynomials
approximation theory
constraint theory
algorithms
 
Description We present a polynomial time algorithm for precedence-constrained scheduling problems in which the task graph can be partitioned into large disjoint parts by removing edges with high float, where the float of an edge is defined as the difference between the length of the longest path in the graph and the length of the longest path containing the edge. Our algorithm guarantees schedules within a factor 1.875 of the optimal independent of the number of processors. The best-known factor for this problem and in general is 2-2/p, where p is the number of processors, due to Coffman–Graham. Our algorithm is unusual and considerably different from that of Coffman–Graham and other algorithms in the literature.
 
Publisher Elsevier
 
Date 2009-05-10T09:11:43Z
2011-12-08T07:07:34Z
2011-12-26T13:01:58Z
2011-12-27T05:47:47Z
2009-05-10T09:11:43Z
2011-12-08T07:07:34Z
2011-12-26T13:01:58Z
2011-12-27T05:47:47Z
2003
 
Type Article
 
Identifier Journal of Computer and System Sciences 67(1), 198-208
0022-0000
10.1016/S0022-0000(03)00071-0
http://hdl.handle.net/10054/1337
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1337
 
Language en