In the problem called single resource constraint scheduling, we are given $m$ identical machines and a set of jobs, each needing one machine to be processed as well as a share of a limited renewable resource $R$. A schedule of these jobs is feasible if, at each point in the schedule, the number of machines and resources required by jobs processed at this time is not exceeded. It is NP-hard to approximate this problem with a ratio better than $3/2$. On the other hand, the best algorithm so far has an absolute approximation ratio of $2+\varepsilon$. This paper presents an algorithm with absolute approximation ratio~$(3/2+\varepsilon)$, which closes the gap between inapproximability and best algorithm except for a negligible small~$\varepsilon$.


翻译:在单一资源制约列表问题上,我们得到的是一美元相同的机器和一套工作,每套都需要一台机器处理,以及一定份额的可再生资源。如果在时间表的每个点上,不超过目前所处理的工作所需的机器和资源的数量,这些工作的时间表是可行的。很难用比重大于3/2美元来估计这个问题。另一方面,目前最好的算法的绝对近似率是2美元。本文提供了一种绝对近近似率~(3/2)美元算法,它缩小了目前所处理的机器和最佳算法之间的差距,只有微不足道的少量的1美元除外。

0
下载
关闭预览

相关内容

【KDD2021】图神经网络,NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
专知会员服务
30+阅读 · 2021年6月12日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
47+阅读 · 2020年7月4日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月5日
VIP会员
相关VIP内容
【KDD2021】图神经网络,NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
专知会员服务
30+阅读 · 2021年6月12日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
47+阅读 · 2020年7月4日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员