Geodesic
Approximation scheme for one problem of a~vector subset choice
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 92-100.

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

We consider the following clustering problem: in a given vector set to find a vector subset of cardinality $k$ with the minimal quadratic deviation from its mean. The distances between vectors are defined by the Euclidean metric. We propose an approximation scheme (PTAS) that solves this problem with an arbitrary relative error $\varepsilon$ in time $O(n^{2/\varepsilon+1}(9/\varepsilon)^{3/\varepsilon d})$, where $n$ is the number of vectors in the original set and $d$ is the space dimension. Ill. 1, bibliogr. 4.
Keywords: vector subset choice, cluster analysis, approximation scheme, approximation algorithm. 
@article{DA_2012_19_2_a6,
     author = {V. V. Shenmaier},
     title = {Approximation scheme for one problem of a~vector subset choice},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {92--100},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_2_a6/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - Approximation scheme for one problem of a~vector subset choice
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 92
EP  - 100
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_2_a6/
LA  - ru
ID  - DA_2012_19_2_a6
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T Approximation scheme for one problem of a~vector subset choice
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 92-100
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_2_a6/
%G ru
%F DA_2012_19_2_a6
V. V. Shenmaier. Approximation scheme for one problem of a~vector subset choice. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 92-100. http://geodesic.mathdoc.fr/item/DA_2012_19_2_a6/

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

[2] Kelmanov A. V., Romanchenko S. M., “Priblizhënnyi algoritm resheniya odnoi zadachi poiska podmnozhestva vektorov”, Diskret. analiz i issled. operatsii, 18:1 (2011), 61–69 | MR

[3] Kelmanov A. V., Romanchenko S. M., “Psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podmnozhestva vektorov i klasternogo analiza”, Avtomat. i telemekh., 2012, no. 2, 156–162

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