Towards Tight Lower Bounds for Scheduling Problems
Towards Tight Lower Bounds for Scheduling Problems
复制标题
迈向调度问题的严格下界
DOI：
10.1007/978-3-662-48350-3_11
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Norouzi
中科院分区：
文献类型：
--
作者：
Ahmad Bazzi;A. Norouzi
我们证明了k-部图的结构难度与具有优先约束的排序问题的紧不可逼近结果之间的密切联系。假设文[1]中的二部结构硬度结果是一个自然但非平凡的推广，我们得到了在相同的平行机上最小化优先约束的抢占作业的最大完工时间问题的难度为2−e。这与该问题的最佳逼近保证[6，4]相匹配。假设相同的假设，我们也得到了相关并行机上优先约束作业调度问题的超常不可逼近结果，从而朝着解决Williamson和Shmoys[17]以及Schuurman和Woeginger[14]的十个开放问题列表中的一个开放问题取得了进展。
We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness result of [1], we obtain a hardness of 2 − e for the problem of minimising the makespan for scheduling precedence-constrained jobs with preemption on identical parallel machines. This matches the best approximation guarantee for this problem [6,4]. Assuming the same hypothesis, we also obtain a super constant inapproximability result for the problem of scheduling precedence-constrained jobs on related parallel machines, making progress towards settling an open question in both lists of ten open questions by Williamson and Shmoys [17], and by Schuurman and Woeginger [14].