A Structural Theorem for Center-Based Clustering in High-Dimensional Euclidean Space

摘要

We prove that, for any finite set X in Euclidean space of any dimension and for any fixed ε > 0, there exists a polynomial-cardinality set of points in this space which can be constructed in polynomial time and which contains (1 + ε)-approximations of all the points of space in terms of the distances to every element of X. The proved statement allows to approximate a lot of clustering problems which can be reduced to finding optimal cluster centers in high-dimensional space. In fact, we construct a polynomial-time approximation-preserving reduction of such problems to their discrete versions, in which the desired centers must be selected from a given finite set.