Email this article On the complexity of some partition problems of a finite set of points in Euclidean space into balanced clusters
- Authors: Kel’manov A.V.1,2, Pyatkin 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 488, No 1 (2019)
- Pages: 16-20
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/16157
- DOI: https://doi.org/10.31857/S0869-5652488116-20
- ID: 16157
Cite item
Full Text
Abstract
We consider some problems of partitioning a finite set of N points in d-dimension Euclidean space into two clusters balancing the value of (1) the quadratic variance normalized by a cluster size, (2) the quadratic variance, and (3) the size-weighted quadratic variance. We have proved the NP-completeness of all these problems.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova str., Novosibirsk, 630090
A. V. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Email: artem@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova str., Novosibirsk, 630090
V. I. Khandeev
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Email: khandeev@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova str., Novosibirsk, 630090
References
- Aloise D., Deshpande A., Hansen P., Popat P. // NP-hardness of Euclidean sum-of-squares clustering. Machine Learning. 2009. V. 75. № 2. P. 245-248.
- Papadimitriou C.H. // Worst-Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput. 1981. V. 10. № 3. P. 542-557.
- Masuyama S., Ibaraki T., Hasegawa T. // The computational complexity of the m-center problems in the plane. IEEE Trans. IECE Jpn. 1981. V. 64. № 2. P. 57-64.
- Aggarwal H., Imai N., Katoh N., Suri S. // Finding k points with minimum diameter and related problems. J. Algorithms. 1991. V. 12. № 1. P. 38-56.
- Snedecor G.W., Cochran W.G. // Statistical Methods, Eighth Edition, Iowa State University Press, 1989.
- Garey M.R., Johnson D.S. // Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. San Francisco, 1979.
Supplementary files
