Geodesic
Approximation algorithms for some NP-hard problems of searching a~vectors subsequence
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 27-38

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

Some NP-hard problems of searching a subsequence in a finite sequence of Euclidean vectors are studied. It is assumed that the desired subsequence has a fixed number of vectors which are mutually close under the criterion of minimum sum of squared distances. Moreover, there is an additional requirement that the difference between the numbers of any two consecutive vectors must lie between two given constants. Some effective 2-approximation algorithms for these problems are presented. Bibliogr. 11.
Keywords: searching a vectors subsequence, minimum sum-of-squared distances, clustering, NP-hardness, effective approximation algorithm. 
@article{DA_2012_19_3_a2,
     author = {A. V. Kel'manov and S. M. Romanchenko and S. A. Khamidullin},
     title = {Approximation algorithms for some {NP-hard} problems of searching a~vectors subsequence},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {27--38},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_3_a2/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. M. Romanchenko
AU  - S. A. Khamidullin
TI  - Approximation algorithms for some NP-hard problems of searching a~vectors subsequence
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 27
EP  - 38
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_3_a2/
LA  - ru
ID  - DA_2012_19_3_a2
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. M. Romanchenko
%A S. A. Khamidullin
%T Approximation algorithms for some NP-hard problems of searching a~vectors subsequence
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 27-38
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_3_a2/
%G ru
%F DA_2012_19_3_a2
A. V. Kel'manov; S. M. Romanchenko; S. A. Khamidullin. Approximation algorithms for some NP-hard problems of searching a~vectors subsequence. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 27-38. http://geodesic.mathdoc.fr/item/DA_2012_19_3_a2/