Geodesic
A $2$-approximation polynomial algorithm for one clustering problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 36-45

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

A $2$-approximation algorithm is presented for one NP-hard data analysis problem. Namely, the problem is to partition a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster and the center of the second one is 0. Bibliogr. 16.
Keywords: cluster analysis, search for a vector subset, computational complexity
Mots-clés : approximation polynomial algorithm. 
@article{DA_2013_20_4_a3,
     author = {A. V. Kelmanov and V. I. Khandeev},
     title = {A $2$-approximation polynomial algorithm for one clustering problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {36--45},
     publisher = {mathdoc},
     volume = {20},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/}
}
TY  - JOUR
AU  - A. V. Kelmanov
AU  - V. I. Khandeev
TI  - A $2$-approximation polynomial algorithm for one clustering problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 36
EP  - 45
VL  - 20
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/
LA  - ru
ID  - DA_2013_20_4_a3
ER  - 
%0 Journal Article
%A A. V. Kelmanov
%A V. I. Khandeev
%T A $2$-approximation polynomial algorithm for one clustering problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 36-45
%V 20
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/
%G ru
%F DA_2013_20_4_a3
A. V. Kelmanov; V. I. Khandeev. A $2$-approximation polynomial algorithm for one clustering problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 36-45. http://geodesic.mathdoc.fr/item/DA_2013_20_4_a3/