Geodesic
FPTAS for solving a~problem of search for a~vector subset
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 41-52

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

We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P$=$NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented. Bibliogr. 12.
Keywords: search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS. 
@article{DA_2014_21_3_a4,
     author = {A. V. Kel'manov and S. M. Romanchenko},
     title = {FPTAS for solving a~problem of search for a~vector subset},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--52},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. M. Romanchenko
TI  - FPTAS for solving a~problem of search for a~vector subset
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 41
EP  - 52
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/
LA  - ru
ID  - DA_2014_21_3_a4
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. M. Romanchenko
%T FPTAS for solving a~problem of search for a~vector subset
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 41-52
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/
%G ru
%F DA_2014_21_3_a4
A. V. Kel'manov; S. M. Romanchenko. FPTAS for solving a~problem of search for a~vector subset. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 41-52. http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/