Geodesic
On the Complexity of Some Max--Min Clustering Problems
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 4, pp. 189-198

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TIMM_2018_24_4_a14,
     author = {A. V. Kel'manov and A. V. Pyatkin and V. I. Khandeev},
     title = {On the {Complexity} of {Some} {Max--Min} {Clustering} {Problems}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {189--198},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_4_a14/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
AU  - V. I. Khandeev
TI  - On the Complexity of Some Max--Min Clustering Problems
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 189
EP  - 198
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_4_a14/
LA  - ru
ID  - TIMM_2018_24_4_a14
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Pyatkin
%A V. I. Khandeev
%T On the Complexity of Some Max--Min Clustering Problems
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 189-198
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_4_a14/
%G ru
%F TIMM_2018_24_4_a14
A. V. Kel'manov; A. V. Pyatkin; V. I. Khandeev. On the Complexity of Some Max--Min Clustering Problems. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 4, pp. 189-198. http://geodesic.mathdoc.fr/item/TIMM_2018_24_4_a14/