On polynomial solvability of one quadratic Euclidean clustering problem on a line
- Authors: Kel’manov A.V.1,2, Khandeev V.I.1,2
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
- Novosibirsk State University
- Issue: Vol 487, No 2 (2019)
- Pages: 126-129
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/15456
- DOI: https://doi.org/10.31857/S0869-56524872126-129
- ID: 15456
Cite item
Full Text
Abstract
We consider the problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Email: kelm@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090
V. I. Khandeev
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: khandeev@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090
References
- Fisher R.A. Statistical Methods and Scientific Inference. N.Y.: Hafner, 1956.
- MacQueen J.B. Some Methods for Classification and Analysis of Multivariate Observations. In: Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability. Berkeley: Univ. of California Press, 1967. V. 1. P. 281-297.
- Aloise D., Deshpande A., Hansen P., Popat P. NP hardness of Euclidean Sum-of-Squares Clustering // Mach. Learn. 2009. V. 75. № 2. P. 245-248.
- Rao M. Cluster Analysis and Mathematical Programming // J. Amer. Stat. Assoc. 1971. V. 66. P. 622-626.
- Bellman R. Dynamic Programming. Princeton: Prince-ton Univ. Press, 1957.
- Grønlund A., Larsen K.G., Mathiasen A., Nielsen J.S., Schneider S., Song M. Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. CoRR arXiv:1701.07204 (2017).
- Кельманов А.В., Хамидуллин С.А., Кельманова М.А. Совместное обнаружение и оценивание повторяющегося фрагмента в зашумленной числовой последовательности при заданном числе повторов // Тез. докл. Рос. конф. “Дискретный анализ и исследование операций” (ДАИО-4). Новосибирск: Изд-во ИМ СО РАН, 2004. С. 185.
- Gimadi E.Kh., Kel’manov A.V., Kel’manova M.A., Khamidullin S.A. A Posteriori Detection of a Quasi Periodic Fragment in Numerical Sequences with Given Number of Recurrences // Sib. J. Industrial Math. 2006. V. 9. № 1 (25). P. 55-74.
- 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 Recogn. and Image Anal. 2008. V. 18. № 1. P. 30-42.
- Kel’manov A.V., Khamidullin S.A. Posterior Detection of a Given Number of Identical Subsequences in a Guasi-Periodic Sequence // Comput. Math. Math. Phys. 2001. V. 41. № 5. P. 762-774.
- Kel’manov A.V., Jeon B. A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train // IEEE Trans. Signal Processing. 2004. V. 52. № 3. P. 645-656.
- Carter J.A., Agol E., et al. Kepler 36: A Pair of Planets with Neighboring Orbits and Dissimilar Densities // Science. 2012. V. 337. № 6094. P. 556-559.
- Кельманов А.В., Пяткин И.В. // ДАН. 2009. Т. 471. № 5. С. 590-592.
- Kel’manov A.V., Pyatkin A.V. On a Version of the Problem of Choosing a Vector Subset // J. Appl. Ind. Math. 2009. V. 3. № 4. P. 447-455.
- Kel’manov A. V., Pyatkin A.V. Complexity of Certain Problems of Searching for Subsets of Vectors and Cluster Analysis // Comput. Math. Math. Phys. 2009. V. 49. № 11. P. 1966-1971.