论文标题
$（2+ \ varepsilon）$ - 单台计算机上先发制的流动时间的近似算法
A $(2+\varepsilon)$-approximation algorithm for preemptive weighted flow time on a single machine
论文作者
论文摘要
加权流动时间是调度方面的基本且非常有研究的目标功能。在本文中，我们研究了具有先发制人的一台机器的设置。该输入由一组工作组成，其特征是其处理时间，发布时间和权重，我们希望为它们计算（可能是先发制人的）时间表。目的是最大程度地减少工作的加权流动时间的总和，在该工作的流动时间是其发布日期和完成时间之间的时间。 对于此设置，找到多项式时间$ o（1）$ - 近似算法是一个长期的开放问题。在最近的突破性结果中，如果输入数据是多项式界限的整数，而Feige，Kulkarni和Li（Soda 2019）在此设置中呈现了黑盒，则BATRA，GARG和KUMAR（FOCS 2018）（2018年）发现了这样的算法。最终的近似值是一个（未明确说明的）常数，至少为$ 10.000 $。在本文中，我们将该比率提高到$ 2+\ Varepsilon $。 BATRA，GARG和KUMAR（FOCS 2018）的算法减少了在树上进行多功能的问题，并通过LP-ROUNDing和Dynamic程序解决了所得的实例。取而代之的是，我们首先将问题减少到（不同的）几何问题，同时仅损失了$ 1+ε$，然后通过动态程序将其结果实例求解至$ 2+ε$。特别是，我们的减少确保了某些结构特性，这要归功于我们不需要LP-RONDONDEND方法。 我们认为，我们的结果取得了重大进展，以在单台机器上找到加权流动时间的PTA。
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 $10.000$. In this paper we improve this ratio to $2+\varepsilon$. 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.
