Computational Complexity of the Choice Problemfor Typical Representatives of a Finite Point Setin a Metric Space

We analyze the complexity of one extremal problem of choosing a subset of $$ p $$ points in a given finite set in a metric space. The chosen subset of points is required to describe given clusters in the best way from the point of view of some geometric criterion. This problem is a formalization of one applied problem from data mining that consists in finding a subset of typical representatives of a dataset based on the rival similarity function. We prove that the problem under consideration is NP-hard by polynomially reducing the well-known NP-hard 3D-Matching problem to this one.