Abstract
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.
The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.
It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2+ε. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1+ε, and then solve its resulting instances up to a factor of 2+ε by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.
We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.
The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.
It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2+ε. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1+ε, and then solve its resulting instances up to a factor of 2+ε by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.
We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.
| Original language | English |
|---|---|
| Title of host publication | STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 |
| Subtitle of host publication | [Proceedings] |
| Editors | Samir Khuller, Virginia Vassilevska Williams |
| Publisher | ACM |
| Pages | 1042-1055 |
| Number of pages | 14 |
| ISBN (Electronic) | 9781450380539 |
| DOIs | |
| Publication status | Published - Jun 2021 |
Publication series
| Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
|---|---|
| ISSN (Print) | 0737-8017 |
