Kel’manov, A. V.; Romanchenko, S. M. An approximation algorithm for solving the problem of the search of a subset of vectors. (Russian) Zbl 1249.90189 Diskretn. Anal. Issled. Oper. 18, No. 1, 61-69 (2011). Summary: A problem in data analysis was earlier reduced to the specific NP-hard optimization problem. In this problem, one wants to find a subset of a given set of Euclidean vectors satisfying the following conditions: (1) the required subset must have the given cardinality; and (2) 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 justified. Cited in 2 Documents MSC: 90C20 Quadratic programming Keywords:searching for subset of vectors; NP-hardness; effective approximation algorithm PDFBibTeX XMLCite \textit{A. V. Kel'manov} and \textit{S. M. Romanchenko}, Diskretn. Anal. Issled. Oper. 18, No. 1, 61--69 (2011; Zbl 1249.90189)