Garg, Naveen ; Kumar, Amit ; Muralidhara, V. N.
(2008)
*Minimizing Total Flow-Time: The Unrelated Case*
Lecture Notes in Computer Science, 5369
.
pp. 424-435.
ISSN 0302-9743

Full text not available from this repository.

Official URL: http://doi.org/10.1007/978-3-540-92182-0_39

Related URL: http://dx.doi.org/10.1007/978-3-540-92182-0_39

## Abstract

We consider the problem of minimizing flow-time in the unrelated machines setting. We introduce a notion of (α,β) variability to capture settings where processing times of jobs on machines are not completely arbitrary and give an O(βlogα) approximation for this setting. As special cases, we get (1) an O(k) approximation when there are only k different processing times (2) an O(logP)-approximation if each job can only go on a specified subset of machines, but has the same processing requirement on each such machine. Further, the machines can have different speeds. Here P is the ratio of the largest to the smallest processing requirement, (3) an Open image in new window- approximation algorithm for unrelated machines if we assume that our algorithm has machines which are an ε-factor faster than the optimum algorithm’s machines. We also improve the lower bound on the approximability for the problem of minimizing flow time on parallel machines from Ω(logP/loglogP−−−−−−−−−−−−√) to Ω(log1 − ε P) for any ε> 0.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer Verlag. |

ID Code: | 123538 |

Deposited On: | 30 Sep 2021 09:35 |

Last Modified: | 30 Sep 2021 09:35 |

Repository Staff Only: item control page