Minimizing flow-time on unrelated machines

N. Bansal, J. Kulkarni

Onderzoeksoutput: Boek/rapportRapportAcademic

91 Downloads (Pure)


We consider some 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 $p_{ij}$ on machine $i$. The flow-time of a job is the amount of time the job spends in the system (completion time minus its arrival time), and is one of the most natural quality of service measure. We show the following two results: an $O(\min(\log^2 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.
Originele taal-2Engels
Aantal pagina's17
StatusGepubliceerd - 2014

Publicatie series
Volume1401.7284 [cs.DS]

Vingerafdruk Duik in de onderzoeksthema's van 'Minimizing flow-time on unrelated machines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit