Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space
- Authors: Kel’manov A.V.1,2, Panasenko A.V.1,2, Khandeev V.I.1,2
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Issue: Vol 59, No 5 (2019)
- Pages: 842-850
- Section: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/180598
- DOI: https://doi.org/10.1134/S0965542519050099
- ID: 180598
Cite item
Abstract
Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set, we need to find a cluster (i.e., a subset) of given size that minimizes the sum of the squared distances between the elements of this cluster and its centroid (geometric center). Every point outside this cluster is considered a singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum, over both clusters, of weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of one of the clusters is unknown and is determined as its centroid, while the center of the other cluster is set at some point of space (without loss of generality, at the origin). The weighting factors for both intracluster sums are the given cluster sizes. Parameterized randomized algorithms are presented for both problems. For given upper bounds on the relative error and the failure probability, the parameter value is defined for which both algorithms find approximation solutions in polynomial time. This running time is linear in the space dimension and the size of the input set. The conditions are found under which the algorithms are asymptotically exact and their time complexity is linear in the space dimension and quadratic in the input set size.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
A. V. Panasenko
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: a.v.panasenko@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
V. I. Khandeev
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: khandeev@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
Supplementary files
