论文标题
用于最大程度减少单台机器加权流动时间的PTA
A PTAS for Minimizing Weighted Flow Time on a Single Machine
论文作者
论文摘要
安排文献的一个重要目标是最大程度地减少加权流动时间的总和。为我们提供了一组工作，其中每个作业的特征是释放时间，处理时间和重量。我们的目标是在单台计算机上找到一个先发制的时间表，该时间表可以最大程度地减少工作的加权流动时间的总和，在该机器的完成时间和发布时间之间的时间是工作的流动时间。 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和Li [Soda 2019]将后者变成了多项式时间算法。但是，问题是否允许PTA，仍然是开放的。我们以肯定的方式回答了这个问题，并呈现一个多项式时间（1+EPS） - 单台计算机上加权流动时间的Approximation算法。我们依赖于将问题减少到几何覆盖问题上，该问题是在提到的（2+EPS）-Approximation算法中引入的，在近似值中失去了一个因子1+EPS。但是，与该算法不同，我们完全解决了该问题的结果实例，而不是丢失因子2+EPS。这样做的关键是识别和利用几何覆盖问题实例的结构特性，这是从加权流动时间减少时出现的。
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.
