We contribute the first randomized algorithm that is an integration of arbitrarily many deterministic algorithms for the fully online multiprocessor scheduling with testing problem. When there are two machines, we show that with two component algorithms its expected competitive ratio is already strictly smaller than the best proven deterministic competitive ratio lower bound. Such algorithmic results are rarely seen in the literature. Multiprocessor scheduling is one of the first combinatorial optimization problems that have received numerous studies. Recently, several research groups examined its testing variant, in which each job $J_j$ arrives with an upper bound $u_j$ on the processing time and a testing operation of length $t_j$; one can choose to execute $J_j$ for $u_j$ time, or to test $J_j$ for $t_j$ time to obtain the exact processing time $p_j$ followed by immediately executing the job for $p_j$ time. Our target problem is the fully online version, in which the jobs arrive in sequence so that the testing decision needs to be made at the job arrival as well as the designated machine. We propose an expected $(\sqrt{\varphi + 3} + 1) (\approx 3.1490)$-competitive randomized algorithm as a non-uniform probability distribution over arbitrarily many deterministic algorithms, where $\varphi = \frac {\sqrt{5} + 1}2$ is the Golden ratio. When there are two machines, we show that our randomized algorithm based on two deterministic algorithms is already expected $\frac {3 \varphi + 3 \sqrt{13 - 7\varphi}}4 (\approx 2.1839)$-competitive. Besides, we use Yao's principle to prove lower bounds of $1.6682$ and $1.6522$ on the expected competitive ratio for any randomized algorithm at the presence of at least three machines and only two machines, respectively, and prove a lower bound of $2.2117$ on the competitive ratio for any deterministic algorithm when there are only two machines.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
Recent advances in deep learning theory
Arxiv
50+阅读 · 2020年12月20日
VIP会员
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员