In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has to wait between the two jobs if they are scheduled on different machines. The objective is to assign the jobs to machines to minimize the makespan of the schedule. Despite being a fundamental problem in theory and a consequential problem in practice, the approximability of scheduling problems with communication delays is not very well understood. One of the top ten open problems in scheduling theory, in the influential list by Schuurman and Woeginger and its latest update by Bansal, asks if the problem admits a constant factor approximation algorithm. In this paper, we answer the question in negative by proving that there is a logarithmic hardness for the problem under the standard complexity theory assumption that NP-complete problems do not admit quasi-polynomial time algorithms. Our hardness result is obtained using a surprisingly simple reduction from a problem that we call Unique Machine Precedence constraints Scheduling (UMPS). We believe that this problem is of central importance in understanding the hardness of many scheduling problems and conjecture that it is very hard to approximate. Among other things, our conjecture implies a logarithmic hardness of related machine scheduling with precedences, a long-standing open problem in scheduling theory and approximation algorithms.


翻译:在非统一通信延迟问题的日程安排中,输入是一组具有先验限制的工种。与一对工作之间每个先验的限制相关的是通信延迟,调度员必须在两个工作之间等待的时间期限,如果这两个工作被安排在不同的机器上。目标是将工作分配到机器上,以最大限度地减少时间表的缩略图。尽管在理论上是一个根本问题,在实践中也随之产生一个问题,但通信延迟的时间安排问题的近似性却不十分清楚。排期理论的前十大开放问题之一,在Shuurman和Woesanginger的有影响力的名单上,以及Bansal的最新更新中,要求问题是否承认一个不变要素近似算法。在本文件中,我们否定了这个问题的答案是:根据标准的复杂理论假设,即NP的完全问题并不接纳准极极权性的时间算法,但我们的难度的结果是利用我们称之为“奇异机器先验”的列表和Bansulding (UMPS) 最新更新的列表中一个令人惊讶的偏差性问题,我们认为,而机算性最接近于一个与此相关的逻辑的逻辑上的逻辑安排问题。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
7+阅读 · 2017年7月11日
Arxiv
0+阅读 · 2021年6月21日
Arxiv
0+阅读 · 2021年6月18日
Arxiv
6+阅读 · 2018年11月29日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
7+阅读 · 2017年7月11日
Top
微信扫码咨询专知VIP会员