会员服务
近似 · 情景 · 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
专知会员服务
85+阅读 · 2021年12月9日
深度概率图模型，Deep Probabilistic Models
专知会员服务
28+阅读 · 2021年8月2日
【Java实现遗传算法】162页pdf，Genetic Algorithms in Java Basics
【Java实现遗传算法】162页pdf，Genetic Algorithms in Java Basics
专知会员服务
43+阅读 · 2020年7月19日
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
专知会员服务
119+阅读 · 2020年5月30日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
【ICLR2020-MIT】元学习的好奇心算法，Meta-learning curiosity algorithms
【ICLR2020-MIT】元学习的好奇心算法，Meta-learning curiosity algorithms
专知会员服务
33+阅读 · 2020年3月13日
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
专知会员服务
133+阅读 · 2020年2月25日
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
专知会员服务
10+阅读 · 2020年1月17日
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
专知会员服务
45+阅读 · 2019年11月15日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
9+阅读 · 2019年10月24日
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
专知
18+阅读 · 2020年5月30日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
美国俄克拉荷马大学电子与计算机工程系招聘博士后
美国俄克拉荷马大学电子与计算机工程系招聘博士后
科研圈
3+阅读 · 2018年8月24日
Soft-NMS – Improving Object Detection With One Line of Code
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
lightgbm algorithm case of kaggle（上）
lightgbm algorithm case of kaggle（上）
R语言中文社区
8+阅读 · 2018年3月20日
【论文】变分推断（Variational inference)的总结
【论文】变分推断（Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
[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日
Generalized Unrelated Machine Scheduling Problem
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日
Stable approximation of Helmholtz solutions by evanescent plane waves
Arxiv
0+阅读 · 2022年2月11日
Mitigating Bias in Calibration Error Estimation
Arxiv
0+阅读 · 2022年2月11日
Domain Specific Approximation for Object Detection
Arxiv
5+阅读 · 2018年10月4日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
近似
情景
CASE
相互独立的
优化器
相关VIP内容
【硬核书】矩阵代数基础，248页pdf
【硬核书】矩阵代数基础，248页pdf
专知会员服务
85+阅读 · 2021年12月9日
深度概率图模型，Deep Probabilistic Models
专知会员服务
28+阅读 · 2021年8月2日
【Java实现遗传算法】162页pdf，Genetic Algorithms in Java Basics
【Java实现遗传算法】162页pdf，Genetic Algorithms in Java Basics
专知会员服务
43+阅读 · 2020年7月19日
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
专知会员服务
119+阅读 · 2020年5月30日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
【ICLR2020-MIT】元学习的好奇心算法，Meta-learning curiosity algorithms
【ICLR2020-MIT】元学习的好奇心算法，Meta-learning curiosity algorithms
专知会员服务
33+阅读 · 2020年3月13日
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
专知会员服务
133+阅读 · 2020年2月25日
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
【AAAI2020】拓扑贝叶斯优化与持久性图：Topological Bayesian Optimization with Persistence Diagrams
专知会员服务
10+阅读 · 2020年1月17日
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
专知会员服务
45+阅读 · 2019年11月15日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
9+阅读 · 2019年10月24日
热门VIP内容
相关资讯
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》
专知
18+阅读 · 2020年5月30日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
美国俄克拉荷马大学电子与计算机工程系招聘博士后
美国俄克拉荷马大学电子与计算机工程系招聘博士后
科研圈
3+阅读 · 2018年8月24日
Soft-NMS – Improving Object Detection With One Line of Code
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
lightgbm algorithm case of kaggle（上）
lightgbm algorithm case of kaggle（上）
R语言中文社区
8+阅读 · 2018年3月20日
【论文】变分推断（Variational inference)的总结
【论文】变分推断（Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
[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日
Generalized Unrelated Machine Scheduling Problem
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日
Stable approximation of Helmholtz solutions by evanescent plane waves
Arxiv
0+阅读 · 2022年2月11日
Mitigating Bias in Calibration Error Estimation
Arxiv
0+阅读 · 2022年2月11日
Domain Specific Approximation for Object Detection
Arxiv
5+阅读 · 2018年10月4日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
Top
微信扫码咨询专知VIP会员
Top