We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, set cover, center selection, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case. All proofs are uniformly invariant based.


翻译:我们首次正式核实了NP-完全优化问题的近似算法:顶点覆盖、独立设置、设置覆盖、中心选择、负载平衡和垃圾包装。 我们发现现有证据的不完善之处,并改进了一个案例中的近似比。 所有证据都以不变为基础。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
专知会员服务
28+阅读 · 2021年8月2日
【Java实现遗传算法】162页pdf,Genetic Algorithms in Java Basics
专知会员服务
43+阅读 · 2020年7月19日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
时间序列算法ARIMA介绍
凡人机器学习
5+阅读 · 2017年6月2日
Arxiv
0+阅读 · 2022年2月13日
Arxiv
0+阅读 · 2022年2月13日
Arxiv
0+阅读 · 2022年2月12日
Arxiv
0+阅读 · 2022年2月11日
Arxiv
5+阅读 · 2018年10月4日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
时间序列算法ARIMA介绍
凡人机器学习
5+阅读 · 2017年6月2日
Top
微信扫码咨询专知VIP会员