CMU-CS-03-103Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-03-103
Nikhil Bansal January 2003
CMU-CS-03-103.ps
Keywords: Flow time, multiple machines, approximation schemes,
preemption, unrelated machines, approximation algorithms
For minimizing total flow time, we give an algorithm which produces a
1 + epsilon approximate solution in time $n^O(m\log{n}\epsilon^2).
For minimizing the maximum flow time, we give a PTAS for a constant number of unrelated machines. 10 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |