Better Algorithms for Minimizing Average Flow-Time on Related Machines

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