No Coreset, No Cry: II
No Coreset, No Cry: II
复制标题
无核心集，无哭泣：II
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Kasturi R. Varadarajan
中科院分区：
文献类型：
--
作者：
M. Edwards;Kasturi R. Varadarajan
设P是d维欧氏空间中的n个点的集合，其中每个点的坐标都在[-Δ，Δ]范围内，其中Δ ≥ 2。设e > 0为给定参数。我们证明了存在P的子集Q，其大小是（log Δ）/e的多项式，使得对于覆盖Q的任何k个板，它们的e-展开覆盖P。集合Q也可以被有效地计算，在时间上大约是Q的大小的界限的n倍。除了对k-板覆盖问题给出n为线性和log Δ为多项式的近似算法外，该结果还对其他几个聚类问题给出了小的核心集和有效的算法。
Let P be a set of n points in d-dimensional Euclidean space, where each of the points has integer coordinates from the range [−Δ, Δ], for some Δ ≥ 2. Let e > 0 be a given parameter. We show that there is subset Q of P, whose size is polynomial in (log Δ)/e, such that for any k slabs that cover Q, their e-expansion covers P. In this result, k and d are assumed to be constants. The set Q can also be computed efficiently, in time that is roughly n times the bound on the size of Q. Besides yielding approximation algorithms that are linear in n and polynomial in log Δ for the k-slab cover problem, this result also yields small coresets and efficient algorithms for several other clustering problems.