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

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


翻译：我们首次正式核实了NP-完全优化问题的近似算法:顶层覆盖、独立设置、设置覆盖、负载平衡和垃圾包装。 我们发现了现有证据的不完善之处,并改进了一个国家的近似比。
0
下载
关闭预览

相关内容

深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
专知会员服务
133+阅读 · 2021年6月16日
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知会员服务
74+阅读 · 2021年1月10日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
不可错过！UIUC最新《统计强化学习》课程！
专知会员服务
52+阅读 · 2020年9月7日
【经典书】算法C语言实现，Algorithms in C. 672页pdf
【经典书】算法C语言实现，Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
【综述】超参数优化:算法和应用综述，Hyper-Parameter Optimization: A Review of Algorithms and Applications
【综述】超参数优化:算法和应用综述，Hyper-Parameter Optimization: A Review of Algorithms and Applications
专知会员服务
55+阅读 · 2020年3月13日
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
专知会员服务
133+阅读 · 2020年2月25日
【2020新书】C语言算法导论，Introducing Algorithms in C，174页pdf
【2020新书】C语言算法导论，Introducing Algorithms in C，174页pdf
专知会员服务
100+阅读 · 2020年2月1日
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
专知会员服务
44+阅读 · 2019年11月15日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
已删除
已删除
将门创投
3+阅读 · 2019年11月25日
目标检测之非极大值抑制(NMS)各种变体
目标检测之非极大值抑制(NMS)各种变体
极市平台
3+阅读 · 2019年5月2日
强化学习的Unsupervised Meta-Learning
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月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日
Guided Exploration with Proximal Policy Optimization using a Single Demonstration
Arxiv
0+阅读 · 2021年6月16日
Projective Resampling Imputation Mean Estimation Method for Missing Covariates Problem
Arxiv
0+阅读 · 2021年6月16日
Optimal sampling for design-based estimators of regression models
Arxiv
0+阅读 · 2021年6月16日
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Arxiv
0+阅读 · 2021年6月15日
Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning
Arxiv
0+阅读 · 2021年6月15日
Linear-Time Probabilistic Solutions of Boundary Value Problems
Arxiv
0+阅读 · 2021年6月14日
Hyper-Parameter Optimization: A Review of Algorithms and Applications
Hyper-Parameter Optimization: A Review of Algorithms and Applications
Arxiv
16+阅读 · 2020年3月12日
Imbalance Problems in Object Detection: A Review
Arxiv
24+阅读 · 2020年3月11日
Approximation Ratios of Graph Neural Networks for Combinatorial Problems
Arxiv
7+阅读 · 2019年5月24日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
近似
情景
CASE
相互独立的
优化器
相关VIP内容
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
专知会员服务
133+阅读 · 2021年6月16日
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知会员服务
74+阅读 · 2021年1月10日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
不可错过！UIUC最新《统计强化学习》课程！
专知会员服务
52+阅读 · 2020年9月7日
【经典书】算法C语言实现，Algorithms in C. 672页pdf
【经典书】算法C语言实现，Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
【综述】超参数优化:算法和应用综述，Hyper-Parameter Optimization: A Review of Algorithms and Applications
【综述】超参数优化:算法和应用综述，Hyper-Parameter Optimization: A Review of Algorithms and Applications
专知会员服务
55+阅读 · 2020年3月13日
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
【经典书】算法设计与分析，727页pdf，Algorithms Design and Analysis，牛津大学出版社
专知会员服务
133+阅读 · 2020年2月25日
【2020新书】C语言算法导论，Introducing Algorithms in C，174页pdf
【2020新书】C语言算法导论，Introducing Algorithms in C，174页pdf
专知会员服务
100+阅读 · 2020年2月1日
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
【目标检测 | 2019最新综述】目标检测中的不平衡问题，附31页PDF， Imbalance Problems in Object Detection: A Review
专知会员服务
44+阅读 · 2019年11月15日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
热门VIP内容
相关资讯
已删除
已删除
将门创投
3+阅读 · 2019年11月25日
目标检测之非极大值抑制(NMS)各种变体
目标检测之非极大值抑制(NMS)各种变体
极市平台
3+阅读 · 2019年5月2日
强化学习的Unsupervised Meta-Learning
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月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日
相关论文
Guided Exploration with Proximal Policy Optimization using a Single Demonstration
Arxiv
0+阅读 · 2021年6月16日
Projective Resampling Imputation Mean Estimation Method for Missing Covariates Problem
Arxiv
0+阅读 · 2021年6月16日
Optimal sampling for design-based estimators of regression models
Arxiv
0+阅读 · 2021年6月16日
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Arxiv
0+阅读 · 2021年6月15日
Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning
Arxiv
0+阅读 · 2021年6月15日
Linear-Time Probabilistic Solutions of Boundary Value Problems
Arxiv
0+阅读 · 2021年6月14日
Hyper-Parameter Optimization: A Review of Algorithms and Applications
Hyper-Parameter Optimization: A Review of Algorithms and Applications
Arxiv
16+阅读 · 2020年3月12日
Imbalance Problems in Object Detection: A Review
Arxiv
24+阅读 · 2020年3月11日
Approximation Ratios of Graph Neural Networks for Combinatorial Problems
Arxiv
7+阅读 · 2019年5月24日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
Top
微信扫码咨询专知VIP会员
Top