An approximation algorithm for solving a problem of search for a vector subset
- 1 January 2012
- journal article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 6 (1), 90-96
- https://doi.org/10.1134/s1990478912010097
Abstract
One of the problems in data analysis was earlier reduced to a specific NP-hard optimization problem of finding in a given vector set in the Euclidean space a subset of a given cardinality such that the subset consists of the vectors that are “close” to each other by the criterion of the minimum sum of squared distances. In the paper an efficient 2-approximation algorithm is proposed for solving this problem.Keywords
This publication has 2 references indexed in Scilit:
- NP-completeness of some problems of choosing a vector subsetJournal of Applied and Industrial Mathematics, 2011
- A Method for Cluster AnalysisBiometrics, 1965