Geodesic
The approximation algorithm for one problem of searching for subset of vectors
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 61-69.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2011_18_1_a5,
     author = {A. V. Kel'manov and S. M. Romanchenko},
     title = {The approximation algorithm for one problem of searching for subset of vectors},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {61--69},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_1_a5/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. M. Romanchenko
TI  - The approximation algorithm for one problem of searching for subset of vectors
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 61
EP  - 69
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_1_a5/
LA  - ru
ID  - DA_2011_18_1_a5
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. M. Romanchenko
%T The approximation algorithm for one problem of searching for subset of vectors
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 61-69
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_1_a5/
%G ru
%F DA_2011_18_1_a5
A. V. Kel'manov; S. M. Romanchenko. The approximation algorithm for one problem of searching for subset of vectors. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 61-69. http://geodesic.mathdoc.fr/item/DA_2011_18_1_a5/

[1] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskret. analiz i issled. operatsii, 17:5 (2010), 37–45

[2] Edwards A. W. F., Cavalli-Sforza L. L., “A method for cluster analysis”, Biometrics, 21 (1965), 362–375 | DOI

[3] Wirth H., Algorithms+data structures=programs, Prentice Hall, New Jersey, 1976, 366 pp. | MR | Zbl