Abstract:
We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P$=$NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented. Bibliogr. 12.
Keywords:search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.