经核实的相近度 (Verified Approximation Algorithms) - 专知论文

会员服务 ·

0

近似 · 情景 · CASE · 相互独立的 · 优化器 ·

2021 年 12 月 13 日

Verified Approximation Algorithms

翻译：经核实的相近度

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

专知会员服务

81+阅读 · 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

专知会员服务

42+阅读 · 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

专知会员服务

244+阅读 · 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，牛津大学出版社

专知会员服务

130+阅读 · 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

专知会员服务

43+阅读 · 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

专知会员服务

8+阅读 · 2019年10月24日

(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》

(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》

专知

17+阅读 · 2020年5月30日

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

23+阅读 · 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会员

文章信息

相关主题

相互独立的

相关VIP内容

【硬核书】矩阵代数基础，248页pdf

【硬核书】矩阵代数基础，248页pdf

专知会员服务

81+阅读 · 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

专知会员服务

42+阅读 · 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

专知会员服务

244+阅读 · 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，牛津大学出版社

专知会员服务

130+阅读 · 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

专知会员服务

43+阅读 · 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

专知会员服务

8+阅读 · 2019年10月24日

热门VIP内容

相关资讯

(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》

(普林斯顿讲义)：高维概率论，326页pdf《Probability in High Dimension》

专知

17+阅读 · 2020年5月30日

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

23+阅读 · 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会员