Geodesic
Approximation algorithm for one problem of partitioning a~sequence
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 53-66.

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

We consider one NP-hard problem of partitioning of a finite Euclidean vectors sequence into two clusters minimizing the sum of squared distances from the clusters elements to their centers. The cardinalities of the clusters are fixed. The center of the first cluster is defined as the mean value of all vectors in a cluster. The center of the second cluster is given in advance and is equal to 0. Additionally, the partition must satisfy the restriction that for all vectors that are in the first cluster the difference between the indices of two consequent vectors from this cluster is bounded from below and above by some constants. An effective $2$-approximation algorithm for the problem is presented. Bibliogr. 9.
Keywords: Euclidean vectors sequence, сlusterization, minimum sum-of-squared distances, NP-hardness, effective $2$-approximation algorithm. 
@article{DA_2014_21_1_a4,
     author = {A. V. Kelmanov and S. A. Khamidullin},
     title = {Approximation algorithm for one problem of partitioning a~sequence},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {53--66},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_1_a4/}
}
TY  - JOUR
AU  - A. V. Kelmanov
AU  - S. A. Khamidullin
TI  - Approximation algorithm for one problem of partitioning a~sequence
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 53
EP  - 66
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_1_a4/
LA  - ru
ID  - DA_2014_21_1_a4
ER  - 
%0 Journal Article
%A A. V. Kelmanov
%A S. A. Khamidullin
%T Approximation algorithm for one problem of partitioning a~sequence
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 53-66
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_1_a4/
%G ru
%F DA_2014_21_1_a4
A. V. Kelmanov; S. A. Khamidullin. Approximation algorithm for one problem of partitioning a~sequence. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 53-66. http://geodesic.mathdoc.fr/item/DA_2014_21_1_a4/

[1] Kel'manov A. V., Pyatkin A. V., “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Physics, 49:11 (2009), 1966–1971 | DOI | MR

[2] Kel'manov A. V., Pyatkin A. V., “On complexity of some problems of cluster analysis of vector sequences”, J. Appl. Industr. Math., 7:3 (2013), 363–369 | DOI | MR | MR

[3] Kel'manov A. V., Romanchenko S. M., “An approximation algorithm for solving a problem of search for a vector subset”, J. Appl. Industr. Math., 6:1 (2012), 90–96 | DOI | MR | Zbl

[4] Kel'manov A. V., Khamidullin S. A., “Posterior detection of a given number of identical subsequences in a quasi-periodic sequence”, Comput. Math. Math. Physics, 41:5 (2001), 762–774 | MR | Zbl

[5] Aloise D., Deshpande A., Hansen P., Popat P., NP-hardness of Euclidean sum-of-squares clustering, Les Cahiers du GERAD, G-2008-33, 2008, 4 pp.

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

[7] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[8] 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

[9] 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