On polynomial solvability of one quadratic Euclidean clustering problem on a line

Cover Page

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

  1. Fisher R.A. Statistical Methods and Scientific Inference. N.Y.: Hafner, 1956.
  2. 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.
  3. 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.
  4. Rao M. Cluster Analysis and Mathematical Programming // J. Amer. Stat. Assoc. 1971. V. 66. P. 622-626.
  5. Bellman R. Dynamic Programming. Princeton: Prince-ton Univ. Press, 1957.
  6. 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).
  7. Кельманов А.В., Хамидуллин С.А., Кельманова М.А. Совместное обнаружение и оценивание повторяющегося фрагмента в зашумленной числовой последовательности при заданном числе повторов // Тез. докл. Рос. конф. “Дискретный анализ и исследование операций” (ДАИО-4). Новосибирск: Изд-во ИМ СО РАН, 2004. С. 185.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. Кельманов А.В., Пяткин И.В. // ДАН. 2009. Т. 471. № 5. С. 590-592.
  14. 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.
  15. 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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2019 Russian academy of sciences

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies