论文标题
通过组合算法朝PTA进行PROS限制的计划。
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms
论文作者
论文摘要
我们研究了在$ m = o（1）$机器上安排$ n $优先限制的单位大小作业的经典问题，以最大程度地减少makepan。在最近的突破中，Levey和Rothvoss \ cite {lr16}开发了一个$（1+ε）$ - 运行时间的问题的近似值$ \ exp \ exp \ big（\ exp \ big big（\ big big） $ \ exp \ big（o \ big（\ frac {m^2} {ε^2} \ log^2 \ log n \ big big）\ big）$ big）$ big（\ frac {m^2} {m^2} {m^2} \ big） GARG \ CITE {GARG18}最近将级别的数量提高到$ \ log^{o（m^2/ε^2）} n $，因此运行时间到$ \ exp \ big big（\ log^{o（m^2/ε^2）n \ big）$ $ m $ $ m $ m $ m。 在本文中，我们提出了一种实现$（1+ε）$的算法 - 运行时间$ n^{o \ left（\ frac {m^4} {m^4} {ε^3} \ log^3 \ log^3 \ log n \ right）} $，非常接近contance $ m $ $ m $和$ m $。与基于线性编程层次结构的Levey-Rothvoss和Garg的算法不同，我们的算法纯粹是组合。对于此问题，我们表明，可以通过猜测最佳时间表来代替提起的LP解决方案上的调理操作。
We study the classic problem of scheduling $n$ precedence constrained unit-size jobs on $m = O(1)$ machines so as to minimize the makespan. In a recent breakthrough, Levey and Rothvoss \cite{LR16} developed a $(1+ε)$-approximation for the problem with running time $\exp\Big(\exp\Big(O\big(\frac{m^2}{ε^2}\log^2\log n\big)\Big)\Big)$, via the Sherali-Adams lift of the basic linear programming relaxation for the problem by $\exp\Big(O\big(\frac{m^2}{ε^2}\log^2\log n\big)\Big)$ levels. Garg \cite{Garg18} recently improved the number of levels to $\log ^{O(m^2/ε^2)}n$, and thus the running time to $\exp\big(\log ^{O(m^2/ε^2)}n\big)$, which is quasi-polynomial for constant $m$ and $ε$. In this paper we present an algorithm that achieves $(1+ε)$-approximation for the problem with running time $n^{O\left(\frac{m^4}{ε^3}\log^3\log n\right)}$, which is very close to a polynomial for constant $m$ and $ε$. Unlike the algorithms of Levey-Rothvoss and Garg, which are based on linear-programming hierarchy, our algorithm is purely combinatorial. For this problem, we show that the conditioning operations on the lifted LP solution can be replaced by making guesses about the optimum schedule.
