An important objective in scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. The currently best known polynomial time algorithm for the problem is a (2+eps)-approximation by Rohwedder and Wiese [STOC 2021] which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS. We answer this question in the affirmative and present a polynomial time (1+eps)-approximation algorithm for weighted flow time on a single machine. We rely on a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+eps)-approximation algorithm, losing a factor 1+eps in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of this problem exactly, rather than losing a factor 2+eps. Key for this is to identify and exploit structural properties of instances of the geometric covering problem which arise in the reduction from weighted flow time.
翻译:列表文献的一个重要目标是将加权流动时间的总数最小化。 我们得到了一组工作, 其中每个工作都具有释放时间、 处理时间和重量的特征。 我们的目标是在一台机器上找到一个先发制人的时间表, 以最小化工作加权流动时间的总和, 工作的流动时间是其完成时间到发布时间之间的时间。 目前最著名的多球时间算法是 Rohwedder 和 Wiesea [STOC 2021] 的匹配 。 我们用肯定性回答这个问题, 并用Batra、 Garg 和 Kumar [FOCS 2018] 之前的突破性结果为基础。 他找到了第一个假极时常因时间的加权流动时间, 并找到了Feige、 Kulkarni 和Li[SODOD/20199] 的结果, 将后者转化为一个多球时间算法。 但是, 问题是否承认 PTASS 存在问题。 我们用肯定性回答这个问题, 并且现在用一个多球时间( 1+) 亚缩缩缩缩缩缩缩算的逻辑, 我们依靠一个算算算算算算算的2 。