Given a point set P in 2D, the problem of finding the smallest set of unit disks that cover all of P is NP-hard. We present a simple algorithm for this problem with an approximation factor of 25/6 in the Euclidean norm and 2 in the max norm, by restricting the disk centers to lie on parallel lines. The run time and space of this algorithm is O(n log n) and O(n) respectively. This algorithm extends to any Lp norm and is asymptotically faster than known alternative approximation algorithms for the same approximation factor.


翻译:从 2D 中的点设置为 P, 找到覆盖 P 全部 P 的最小的一组单盘的问题就是 NP- hard 。 我们对此问题提出了一个简单的算法, 在 Euclidean 规范中, 近似系数为 25/6, 最大值为 2, 其方法是将磁盘中心限制在平行线上。 此算法的运行时间和空间分别是 O(n log n) 和 O(n) 。 此算法扩展至任何 Lp 规范, 并且比已知的相同近似系数的替代近似算法要快。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
论文浅尝 | Improved Neural Relation Detection for KBQA
开放知识图谱
13+阅读 · 2018年1月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
5+阅读 · 2018年10月4日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关资讯
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
论文浅尝 | Improved Neural Relation Detection for KBQA
开放知识图谱
13+阅读 · 2018年1月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员