|
This article is cited in 3 scientific papers (total in 3 papers)
On the Complexity of Some Max–Min Clustering Problems
A. V. Kel'manovab, A. V. Pyatkinab, V. I. Khandeevab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
Abstract:
Two similar problems of searching for a family of disjoint subsets
(clusters) in a finite set of points in Euclidean space are considered. In these
problems, the size of the smallest cluster should be maximized so that in each
cluster the intracluster quadratic variation of the points with respect to the
center of the cluster would not exceed a given (constant) fraction of the total quadratic
variation of the points of the input set with respect to its centroid.
In the first problem, the centers of intracluster variations are arbitrary
points of the space given at the input. In the second problem, the centers of
the intracluster variation are unknown (to be found) but must lie in the
input set. Both problems are proved to be NP-hard even on the real line
both in the general case when the number of the clusters is a part of the input
and in the parametric case when the number of the clusters is fixed.
Keywords:
Euclidean space, clustering, max–min problem, quadratic variation, NP-hardness.
Received: 30.07.2018 Revised: 08.10.2018 Accepted: 12.11.2018
Citation:
A. V. Kel'manov, A. V. Pyatkin, V. I. Khandeev, “On the Complexity of Some Max–Min Clustering Problems”, Trudy Inst. Mat. i Mekh. UrO RAN, 24, no. 4, 2018, 189–198; Proc. Steklov Inst. Math. (Suppl.), 309, suppl. 1 (2020), S65–S73
Linking options:
https://www.mathnet.ru/eng/timm1585 https://www.mathnet.ru/eng/timm/v24/i4/p189
|
|