×

An approximation algorithm for solving the problem of the search of a subset of vectors. (Russian) Zbl 1249.90189

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.

MSC:

90C20 Quadratic programming
PDFBibTeX XMLCite