On the complexity of some quadratic Euclidean 2-clustering problems
- 1 March 2016
- journal article
- Published by Pleiades Publishing Ltd in Computational Mathematics and Mathematical Physics
- Vol. 56 (3), 491-497
- https://doi.org/10.1134/s096554251603009x
Abstract
Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).Keywords
This publication has 14 references indexed in Scilit:
- A 2-approximate algorithm to solve one problem of the family of disjoint vector subsetsAutomation and Remote Control, 2014
- An Introduction to Statistical LearningPublished by Springer Science and Business Media LLC ,2013
- Machine LearningPublished by Cambridge University Press (CUP) ,2012
- On the complexity of some cluster analysis problemsComputational Mathematics and Mathematical Physics, 2011
- On the complexity of some data analysis problemsComputational Mathematics and Mathematical Physics, 2010
- Complexity of certain problems of searching for subsets of vectors and cluster analysisComputational Mathematics and Mathematical Physics, 2009
- NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 2009
- On the complexity of a search for a subset of “similar” vectorsDoklady Mathematics, 2008
- On the Complexity of Clustering ProblemsPublished by Springer Science and Business Media LLC ,1978
- P-Complete Approximation ProblemsJournal of the ACM, 1976