Geodesic
An approximation polynomial-time algorithm for a sequence bi-clustering problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 1076-1085 
A. V. Kel'manov; S. A. Khamidullin. An approximation polynomial-time algorithm for a sequence bi-clustering problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 1076-1085. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/
@article{ZVMMF_2015_55_6_a13,
     author = {A. V. Kel'manov and S. A. Khamidullin},
     title = {An approximation polynomial-time algorithm for a sequence bi-clustering problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1076--1085},
     year = {2015},
     volume = {55},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. A. Khamidullin
TI  - An approximation polynomial-time algorithm for a sequence bi-clustering problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 1076
EP  - 1085
VL  - 55
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/
LA  - ru
ID  - ZVMMF_2015_55_6_a13
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. A. Khamidullin
%T An approximation polynomial-time algorithm for a sequence bi-clustering problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 1076-1085
%V 55
%N 6
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/
%G ru
%F ZVMMF_2015_55_6_a13

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

We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in Euclidean space into two clusters using the criterion of the minimal sum of the squared distances from the elements of the clusters to the centers of the clusters. The center of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The center of the other cluster is fixed at the origin. Moreover, the partition is such that the difference between the indices of two successive vectors in the first cluster is bounded above and below by prescribed constants. A 2-approximation polynomial-time algorithm is proposed for this problem.

[1] Kelmanov A. V., Pyatkin A. V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. AN, 421:5 (2008), 590–592 | Zbl

[2] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 49:11 (2009), 2059–2067 | MR

[3] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach klasternogo analiza vektornykh posledovatelnostei”, Diskret. analiz i issled. operatsii, 20:2 (2013), 47–57 | MR

[4] Anil K., Jain K., “Data clustering: 50 years beyond $k$-means”, Pat. Recognit. Let., 31 (2010), 651–666

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

[6] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of euclidean sum-of-squares clustering”, Machine Learn., 75:2 (2009), 245–248

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

[8] Carter J. A., Agol E. et al., “Kepler-36: A pair of planets with neighboring orbits and dissimilar densities”, Sci., 337:6094 (2012), 556–559

[9] Carter J. A., Agol E., “The quasiperiodic automated transit search algorithm”, The Astrophysic. J., 765:2 (2013) | DOI

[10] Kelmanov A. V., “Problema off-line obnaruzheniya povtoryayuschegosya fragmenta v chislovoi posledovatelnosti”, Tr. In-ta matem. i mekhan. UrO RAN, 14, no. 2, 2008, 81–88 | Zbl

[11] Garey M. R., Johnson D. S., Computers and intractability: A Guide to the theory of NP-completeness, Freeman, San Francisco, 1979 | MR | Zbl

[12] Kelmanov A. V., Khandeev V. I., “Polinomialnyi algoritm s otsenkoi tochnosti 2 dlya resheniya odnoi zadachi klasternogo analiza”, Diskret. analiz i issled. operatsii, 20:4 (2013), 36–45 | MR

[13] Kelmanov A. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zh. vychisl. matem. i matem. fiz., 41:5 (2001), 807–820 | MR | Zbl

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