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/

[1] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1 (2006), 55–74 | MR | Zbl

[2] Kelmanov A. V., Mikhailova L. V., “Sovmestnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti zadannogo chisla fragmentov iz etalonnogo nabora i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 46:1 (2006), 172–189 | MR | Zbl

[3] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Ob odnoi zadache poiska uporyadochennykh naborov fragmentov v chislovoi posledovatelnosti”, Diskret. analiz i issled. operatsii, 16:4 (2009), 31–46 | MR

[4] Kelmanov A. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zhurn. vychisl. matematiki i mat. fiziki, 41:5 (2001), 807–820 | MR | Zbl

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

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

[7] Shenmaier V. V., “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Matematicheskie metody raspoznavaniya obrazov, 15-ya Vseros. konf. (MMRO-15). Sb. dokl., MAKS Press, M., 2011, 284–286

[8] Anil K., Jain K., “Data clustering: 50 years beyond $k$-means”, Pattern Recognit. Lett., 31 (2010), 651–666 | DOI

[9] Hastie T., Tibshirani R., Friedman J., The elements of statistical learning: data mining, inference, and prediction, Springer-Verl., New York, 2001, 533 pp. | MR | Zbl

[10] Kel'manov A. V., Jeon B., “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Trans. Signal Process, 52:3 (2004), 645–656 | DOI | MR

[11] Kel'manov A. V., Khamidullin S. A., “An algorithm for recognition of a vector alphabet generating a sequence with a quasi-periodic structure”, Pattern Recognit. Image Anal., 20:4 (2010), 451–458 | DOI