标题： 固定维数中基于几何中心的通用离散化的小规模方法 显示英文标题

标题： Linear-Size Universal Discretization of Geometric Center-Based Problems in Fixed Dimensions

摘要： 许多几何优化问题可以归结为寻找空间中的点（中心），以最小化一个连续依赖于中心到给定输入点距离的目标函数。 示例包括 $k$-Means， 几何 $k$-Median/Center，连续设施定位， $m$-Variance 等。 我们证明，对于任何固定的 $\varepsilon>0$，在由任意向量范数诱导的度量的固定维空间中，任何 $n$个输入点都存在一个包含 $O(n)$个候选中心的集合，该集合可以在几乎线性时间内计算，并且包含相对于所有输入点距离的每个空间点的 $(1+\varepsilon)$-近似值。 这为具有任意连续类型目标函数的基于中心的几何问题提供了一个通用的近似保持缩减，将其转化为其中心从一个相当小的候选集选择的离散版本。 对于任何固定膨胀维数的度量空间，也证明了此类线性大小的候选集的存在性。 显示英文摘要

摘要： 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.