会员服务
近似 · 情景 · CASE · 相互独立的 · 优化器 ·
2021 年 12 月 13 日
Verified Approximation Algorithms
翻译：经核实的相近度
Robin Eßmann,Tobias Nipkow,Simon Robillard,Ujkan Sulejmani
Robin Eßmann,Tobias Nipkow,Simon Robillard,Ujkan Sulejmani

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
【硬核书】矩阵代数基础，248页pdf
专知会员服务
88+阅读 · 2021年12月9日
深度概率图模型，Deep Probabilistic Models
专知会员服务
29+阅读 · 2021年8月2日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
251+阅读 · 2020年5月18日
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
专知会员服务
11+阅读 · 2020年1月17日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
10+阅读 · 2019年10月24日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Soft-NMS – Improving Object Detection With One Line of Code
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
[DLdigest-8] 每日一道算法
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
时间序列算法ARIMA介绍
时间序列算法ARIMA介绍
凡人机器学习
5+阅读 · 2017年6月2日
Universal approximation of symmetric and anti-symmetric functions
Arxiv
0+阅读 · 2022年2月15日
Local approximation of operators
Arxiv
0+阅读 · 2022年2月13日
New Approximation Algorithms for Fair $k$-median Problem
Arxiv
0+阅读 · 2022年2月13日
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arxiv
0+阅读 · 2022年2月12日
Formalization of a Stochastic Approximation Theorem
Arxiv
0+阅读 · 2022年2月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
近似
情景
CASE
相互独立的
优化器
相关VIP内容
【硬核书】矩阵代数基础，248页pdf
【硬核书】矩阵代数基础，248页pdf
专知会员服务
88+阅读 · 2021年12月9日
深度概率图模型，Deep Probabilistic Models
专知会员服务
29+阅读 · 2021年8月2日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
251+阅读 · 2020年5月18日
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
专知会员服务
11+阅读 · 2020年1月17日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
10+阅读 · 2019年10月24日
热门VIP内容
相关资讯
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Soft-NMS – Improving Object Detection With One Line of Code
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
[DLdigest-8] 每日一道算法
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
时间序列算法ARIMA介绍
时间序列算法ARIMA介绍
凡人机器学习
5+阅读 · 2017年6月2日
相关论文
Universal approximation of symmetric and anti-symmetric functions
Arxiv
0+阅读 · 2022年2月15日
Local approximation of operators
Arxiv
0+阅读 · 2022年2月13日
New Approximation Algorithms for Fair $k$-median Problem
Arxiv
0+阅读 · 2022年2月13日
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arxiv
0+阅读 · 2022年2月12日
Formalization of a Stochastic Approximation Theorem
Arxiv
0+阅读 · 2022年2月12日
Top
微信扫码咨询专知VIP会员
Top