A randomized algorithm for two-cluster partition of a set of vectors
- 1 February 2015
- journal article
- Published by Pleiades Publishing Ltd in Computational Mathematics and Mathematical Physics
- Vol. 55 (2), 330-339
- https://doi.org/10.1134/s096554251502013x
Abstract
A randomized algorithm is substantiated for the strongly NP-hard problem of partitioning a finite set of vectors of Euclidean space into two clusters of given sizes according to the minimum-of-the sum-of-squared-distances criterion. It is assumed that the centroid of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The centroid of the other cluster is fixed at the origin. For an established parameter value, the algorithm finds an approximate solution of the problem in time that is linear in the space dimension and the input size of the problem for given values of the relative error and failure probability. The conditions are established under which the algorithm is asymptotically exact and runs in time that is linear in the space dimension and quadratic in the input size of the problem.Keywords
This publication has 17 references indexed in Scilit:
- NP-hardness of the Euclidean Max-Cut problemDoklady Mathematics, 2014
- A 2-approximate algorithm to solve one problem of the family of disjoint vector subsetsAutomation and Remote Control, 2014
- 2-Approximation algorithm for finding a clique with minimum weight of vertices and edgesProceedings of the Steklov Institute of Mathematics, 2014
- On the complexity of some cluster analysis problemsComputational Mathematics and Mathematical Physics, 2011
- An approximation algorithm for solving a problem of cluster analysisJournal of Applied and Industrial Mathematics, 2011
- On the algorithmic complexity of a problem in cluster analysisJournal of Applied and Industrial Mathematics, 2011
- Data clustering: 50 years beyond K-meansPattern Recognition Letters, 2009
- NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 2009
- Minimum Sum of Squares Clustering in a Low Dimensional SpaceJournal of Classification, 1998
- Cluster Analysis and Mathematical ProgrammingJournal of the American Statistical Association, 1971