Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem

A. V. Kel'manov ; S. A. Khamidullin ; V. I. Khandeev

Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 21-40.

Résumé

We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into two clusters minimizing the sum over both clusters of intra-cluster sum of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second one is given in advance and is equal to 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by some given constants. We present a fully polynomial-time approximation scheme for the case of fixed space dimension. Bibliogr. 27.

Détail

Keywords: partitioning, sequence, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.

Bibliographie

[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[2] E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space”, J. Appl. Ind. Math., 3:3 (2009), 343–352 | DOI | MR | Zbl

[3] E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension”, J. Appl. Ind. Math., 4:1 (2010), 48–53 | DOI | MR | Zbl

[4] A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558 | DOI | MR | Zbl

[5] A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Tr. Inst. Mat. Mekh., 21, no. 3, 2015, 100–109 | MR

[6] A. V. Kel'manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence”, Proc. Steklov Inst. Math., 263, Suppl. 2 (2008), S84–S92 | MR | Zbl

[7] A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50 (2010), 1941–1947 | DOI | MR | Zbl

[8] A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988 | DOI | MR | Zbl

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

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

[11] A. V. Kel'manov, S. M. Romanchenko, “An FPTAS for a vector subset search problem”, J. Appl. Ind. Math., 8:3 (2014), 329–336 | DOI | MR | Zbl

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

[13] A. V. Kel'manov, S. A. Khamidullin, “An approximating polynomial algorithm for a sequence partitioning problem”, J. Appl. Ind. Math., 8:2 (2014), 236–244 | DOI | MR | Zbl

[14] A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Comput. Math. Math. Phys., 55:6 (2015), 1068–1076 | DOI | DOI | MR | Zbl

[15] A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “An exact pseudopolynomial algorithm for a sequence bi-clustering problem”, Abstr. XV All-Russ. Conf. “Mathematical Programming and Applications” (Ekaterinburg, Russia, Mar. 2–6, 2015), Inst. Mat. Mekh. UrO RAN, Ekaterinburg, 2015, 139–140

[16] A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339 | DOI | DOI | MR | Zbl

[17] A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors”, J. Appl. Ind. Math., 9:4 (2015), 497–502 | DOI | DOI | MR

[18] A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341 | DOI | DOI | MR | Zbl

[19] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Machine Learning, 75:2 (2009), 245–248 | DOI

[20] Bishop M. C., Pattern recognition and machine learning, Springer-Verl., New York, 2006, 738 pp. | MR | Zbl

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

[22] Flach P., Machine learning: the art and science of algorithms that make sense of data, Cambridge Univ. Press, New York, 2012, 396 pp. | MR | Zbl

[23] Gimadi E. Kh., Kel'manov A. V., Kel'manova M. A., Khamidullin S. A., “A posteriori detecting a quasiperiodic fragment in a numerical sequence”, Pattern Recognit. Image Anal., 18:1 (2008), 30–42 | DOI | MR

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

[25] James G., Witten D., Hastie T., Tibshirani R., An introduction to statistical learning, Springer-Verl., New York, 2013, 426 pp. | MR | Zbl

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

[27] Steger C., Ulrich M., Wiedemann C., Machine vision algorithms and applications, Wiley-VCH, Berlin, 2007, 380 pp.