Name
Abstract | ||
|---|---|---|
We consider some classical flow-time minimization problems in the unrelated machines setting. In this setting, there is a set of m machines and a set of n jobs, and each job j has a machine dependent processing time of pij on machine i. The flow-time of a job is the amount of time the job spends in a system (its completion time minus its arrival time), and is one of the most natural measure of quality of service. We show the following two results: an $O(min(log2 n, log n log P)) approximation algorithm for minimizing the total flow-time, and an O(log n) approximation for minimizing the maximum flow-time. Here P is the ratio of maximum to minimum job size. These are the first known poly-logarithmic guarantees for both the problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2746539.2746601 | symposium on the theory of computing |
Keywords | DocType | Volume |
scheduling | Journal | abs/1401.7284 |
ISSN | Citations | PageRank |
0737-8017 | 5 | 0.42 |
References | Authors | |
25 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Bansal | 1 | 3043 | 230.41 |
| Janardhan Kulkarni | 2 | 28 | 3.34 |