Many geometric optimization problems can be reduced to finding points in space (centers) minimizing an objective function which continuously depends on the distances from the centers to given input points. Examples are $k$-Means, Geometric $k$-Median/Center, Continuous Facility Location, $m$-Variance, etc. We prove that, for any fixed $\varepsilon>0$, every set of $n$ input points in fixed-dimensional space with the metric induced by any vector norm admits a set of $O(n)$ candidate centers which can be computed in almost linear time and which contains a $(1+\varepsilon)$-approximation of each point of space with respect to the distances to all the input points. It gives a universal approximation-preserving reduction of geometric center-based problems with arbitrary continuity-type objective functions to their discrete versions where the centers are selected from a fairly small set of candidates. The existence of such a linear-size set of candidates is also shown for any metric space of fixed doubling dimension.


翻译:许多几何优化问题可以简化为在空间中找到点(中心),最大限度地减少一个持续取决于从中心到特定输入点距离的客观功能,例如,$-Means、几何美元-Median/Center、连续设施位置、百万美元-变化等。我们证明,对于任何固定的$\varepsilon>0美元,固定空间的每一套美元输入点,以及任何矢量规范所引的衡量标准,都承认一套可几乎直线时间计算并包含每个空间点与所有输入点距离的(1 ⁇ varepsilon)相匹配的O(n)美元候选中心。它使具有任意连续性目标功能的几何测中心问题普遍减少到其离散版本,而中心是从相当小的一组候选人中挑选出来的。对于任何固定双维的计量空间,也显示存在一套线性候选人。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
124+阅读 · 2020年6月25日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
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日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
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日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员