A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
复制标题
使用 LP 层次结构的具有优先约束的 Makespan 调度的 A (1 epsilon) 近似
DOI：
10.1137/16m1105049
复制
发表时间：
2019
影响因子：
1.6
通讯作者：
Rothvoss, Thomas
中科院分区：
文献类型：
--
作者：
Levey, Elaine;Rothvoss, Thomas
在一个经典的排序问题中，一个工件具有一个优先顺序，目标是找到一个在中型机器上的工件排序，使最大完工时间最小。这是Garey &约翰逊的书中剩余的四个未解决的问题之一，它是否是NP-难形式= 3.我们证明了对任意固定的ε和m，时间指标LP的LP-层次提升具有略超多对数的r =（log（n））Θ（loglogn）轮数，提供了（1 + ε）-逼近.例如，Sherali-Adams足以作为层次结构。这意味着一个算法，在timenO（r）中产生（1+ε）-近似。以前的最佳近似算法保证了多项式时间形式≥ 4和4/3形式=3的2 − 7/3 m +1-近似。我们的算法是基于递归调度方法，在每一步中，我们减少了长链形式的相关性。我们的方法添加到相当短的列表中的例子，层次结构实际上是有用的，以获得更好的近似算法。
In a classical problem in scheduling, one hasnunit size jobs with aprecedence orderand the goal is to find a schedule of those jobs onmidentical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem isNP-hard form=3.We prove that for any fixed ε andm, an LP-hierarchy lift of the time-index LP with a slightly super poly-logarithmic number ofr= (log(n))Θ(loglogn)rounds provides a (1 + ε)-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a (1+ε)-approximation in timenO(r). The previously best approximation algorithms guarantee a 2 − 7/3m+1-approximation in polynomial time form≥ 4 and 4/3 form=3. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms.