Garg, Naveen ; Kumar, Amit (2006) Better Algorithms for Minimizing Average Flow-Time on Related Machines Lecture Notes in Computer Science, 4051 . pp. 181-190. ISSN 0302-9743
Full text not available from this repository.
Official URL: http://doi.org/10.1007/11786986_17
Related URL: http://dx.doi.org/10.1007/11786986_17
Abstract
We consider the problem of minimising flow time on related machines and give an O(logP)-approximation algorithm for the offline case and an O(log2 P)-competitive algorithm for the online version. This improves upon the previous best bound of O(log2 P logS) on the competitive ratio. Here P is the ratio of the maximum to the minimum processing time of a job and S is the ratio of the maximum to the minimum speed of a machine.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123545 |
| Deposited On: | 30 Sep 2021 10:07 |
| Last Modified: | 30 Sep 2021 10:07 |
Repository Staff Only: item control page
