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/