Abstract:
One problem in data analysis was earlier reduced to the specific NP-hard optimization problem. In this problem one needs to find a subset of given set of Euclidean vectors satisfying the following conditions. Firstly the required subset must have the given cardinality and secondly it should include vectors which are mutually close under the criterion of minimum sum of squared distances. In the paper, an effective 2-approximation algorithm for this problem is proved. Bibliogr. 3.
Keywords:searching for subset of vectors, NP-hardness, effective approximation algorithm.