The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. We also present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.


翻译:优先模式被引入以捕捉“ 贪婪类” 算法。 受在线算法领域咨询复杂程度的成功激励, 固定优先模式被扩展为包括咨询在内的建议复杂性, 固定优先模式被扩展为包括咨询, 并开发了一个基于削减的框架, 以证明在这个相当强大的模型中达到某些近似比率所需的咨询量的下限。 要捕捉被认为贪婪类的、 更强大的适应性优先算法模型的多数算法, 需要更强大的适应性优先模式。 我们扩展适应性优先模式以包括咨询。 我们修改基于削减的框架, 与更强大的适应性优先级算法合作, 简化正确性证明正确性的证据, 强化先前所有较低范围的范围。 我们还提出了一个纯粹的组合性适应性优先性优先级算法, 向最小 Vertexex Clove提供建议。 我们的算法实现了最佳性, 最多为 7n22 位数的适应性优先级算法, 没有建议, 任何基于建议的适应性优先级算法的在线算法需要超过 7n/ 22 位数的运行优化性建议, 并用最优化性算法 和最精确的分级算法 定义,, 在精确级算法中, 中的所有级算法和最精度建议, 的分级算法, 的分级级算法, 确定所有精度 的精度, 的精准性算法和最精度 的精度, 的精度 的精度 精度, 精度, 精度是精确性算法 的精度 的精度,, 精度, 精度, 精度, 精度, 精度和精度是精确性算性算法和精度算法 的精度算性算法和精度, 的精度算法和精度, 的精度 的精度 的精度算法和精度 精度 精度 精度 精度 的精度 精度 精度算法和精度 的精度算法和精度算法和精度算法和精度算法。

0
下载
关闭预览

相关内容

【MIT Sam Hopkins】如何读论文?How to Read a Paper
专知会员服务
105+阅读 · 2022年3月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月17日
VIP会员
相关VIP内容
【MIT Sam Hopkins】如何读论文?How to Read a Paper
专知会员服务
105+阅读 · 2022年3月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员