On the optimality of approximation schemes for the classical scheduling problem
On the optimality of approximation schemes for the classical scheduling problem
复制标题
DOI：
10.1137/1.9781611973402.50
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Lin Chen;K. Jansen;Guochuan Zhang
中科院分区：
文献类型：
--
作者：
Lin Chen;K. Jansen;Guochuan Zhang
以最小化完工时间为目标，我们考虑了经典的平行同型机排序问题，并在指数时间假设(ETH)下得到了如下结果：1.常数$m$的同型机排序问题，记为$pm||C_{max}，它允许运行时间为$O(N)+(1/\epsilon)^{O(M)}$的完全多项式时间近似方案(FPTAS)(实际上，该算法适用于机器无关的更一般的问题)。我们证明了这个算法本质上是最好的，因为对于任何$\Delta&>0$，一个$(1/\epsilon)^{O(m^{1-\Delta})}+n^{O(1)}$time FPTAS意味着ETH失败。2.任意数量的相同机器上的调度问题，记为$P||C_{max}$，已知允许运行时间$2^{O(1/\epsilon^2\log^3(1/\epsilon))}+n^{O(1)}$.的多项式时间近似方案(PTA我们证明了该算法是几乎最优的，因为对任何$\Delta>；0$，$2^{O((1/\epsilon)^{1-\Delta})}+n^{O(1)}$time PTAS意味着ETH失败，留下了很小的改进空间。为了获得这些结果，我们将从3SAT提供两个新的减法，一个是$PM||C_{max}$，另一个是$P||C_{max}$。事实上，新的减员探索了调度问题的结构，还可以产生其他有趣的结果。例如，使用我们对$P||C_{max}$的约简框架，Chen等人。(arxiv：1306.3727)证明了排序为3的作业处理时间矩阵$P=(p_(Ij))_{m\次n}$的调度问题的APX难度，解决了Bhaskara等人提出的公开问题。(苏打水2013)。
We consider the classical scheduling problem on parallel identical machines to minimize the makespan, and achieve the following results under the Exponential Time Hypothesis (ETH) 1. The scheduling problem on a constant number $m$ of identical machines, which is denoted as $Pm||C_{max}$, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time $O(n) + (1/\epsilon)^{O(m)}$ (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a $(1/\epsilon)^{O(m^{1-\delta})}+n^{O(1)}$ time FPTAS for any $\delta>0$ implies that ETH fails. 2. The scheduling problem on an arbitrary number of identical machines, which is denoted as $P||C_{max}$, is known to admit a polynomial time approximation scheme (PTAS) of running time $2^{O(1/\epsilon^2\log^3(1/\epsilon))}+n^{O(1)}$. We prove this algorithm is nearly optimal in the sense that a $2^{O((1/\epsilon)^{1-\delta})}+n^{O(1)}$ time PTAS for any $\delta>0$ implies that ETH fails, leaving a small room for improvement. To obtain these results we will provide two new reductions from 3SAT, one for $Pm||C_{max}$ and another for $P||C_{max}$. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for $P||C_{max}$, Chen et al. (arXiv:1306.3727) is able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times $P=(p_{ij})_{m\times n}$ is of rank 3, solving the open problem mentioned by Bhaskara et al. (SODA 2013).