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.
| Original language | English |
|---|---|
| Title of host publication | STOC 2015 : 47th Annual ACM Symposium on the Theory of Computing, Portland OR, USA, June 14-17, 2015 |
| Editors | R.A. Servedio, R. Rubinfeld |
| Place of Publication | New York NY |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 851-860 |
| ISBN (Print) | 978-1-4503-3536-2 |
| DOIs | |
| Publication status | Published - 2015 |
| Event | 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA - Portland, OR, United States Duration: 14 Jun 2015 → 17 Jun 2015 http://acm-stoc.org/stoc2015/ |
Conference
| Conference | 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA |
|---|---|
| Abbreviated title | STOC 2015 |
| Country/Territory | United States |
| City | Portland, OR |
| Period | 14/06/15 → 17/06/15 |
| Internet address |