Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. V. Kel’manov and A. V. Pyatkin, “On the complexity of a search for a subset of “similar” vectors,” Dokl. Math 78 (1), 574–575 (2008).
A. V. Kel’manov and A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis,” Comput. Math. Math. Phys. 49 (11), 1966–1971 (2009).
A. V. Kel’manov and A. V. Pyatkin, “On complexity of some problems of cluster analysis of vector sequences,” J. Appl. Ind. Math. 7 (3), 363–369 (2013).
K. Anil and K. Jain, “Data clustering: 50 years beyond k-means,” Pattern Recogn. Lett. 31, 651–666 (2010).
T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer, New York, 2001).
D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Machine Learning 75 (2), 245–248 (2009).
A. V. Kel’manov and B. Jeon, “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train,” IEEE Trans. Signal Processing 52 (3), 645–656 (2004).
J. A. Carter, E. Agol, at al., “Kepler-36: A pair of planets with neighboring orbits and dissimilar densities,” Science 337 (6094), 556–559 (2012).
J. A. Carter and E. Agol, “The quasiperiodic automated transit search algorithm,” Astrophys. J. 765 (2) (2013); doi:10.1088/0004-637X/765/2/132.
A. V. Kel’manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence,” Proc. Steklov Inst. Math. 263, Suppl. 2, S84–S92 (2008).
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
A. V. Kel’manov and V. I. Khandeev, “A 2-approximation polynomial algorithm for a clustering problem,” J. Appl. Ind. Math. 7 (4), 515–521 (2013).
A. V. Kel’manov and S. A. Khamidullin, “Posterior detection of a given number of identical subsequences in a quasi-periodic sequence,” Comput. Math. Math. Phys. 41 (5), 762–774 (2001).
A. V. Kel’manov and S. M. Romanchenko, “An approximation algorithm for solving a problem of search for a vector subset,” J. Appl. Ind. Math. 6 (1), 90–96 (2012).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Original Russian Text © A.V. Kel’manov, S.A. Khamidullin, 2015, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2015, Vol. 55, No. 6, pp. 1076–1085.
Rights and permissions
About this article
Cite this article
Kel’manov, A.V., Khamidullin, S.A. An approximation polynomial-time algorithm for a sequence bi-clustering problem. Comput. Math. and Math. Phys. 55, 1068–1076 (2015). https://doi.org/10.1134/S0965542515060068
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542515060068