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
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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{\textendash}Min} {Clustering} {Problems}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {189--198},
     year = {2018},
     volume = {24},
     number = {4},
     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
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
%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/

[1] G. James, D. Witten, T. Hastie, R. Tibshirani, An introduction to statistical learning, Springer Science+Business Media, LLC, N Y, 2013, 426 pp. | MR | Zbl

[2] Aggarwal C. C., Data mining: The textbook, Springer International Publishing, N Y, 2015, 734 pp. | DOI | MR | Zbl

[3] Bishop C. M., Pattern recognition and machine learning, Springer Science+Business Media, LLC, N Y, 2006, 738 pp. | MR | Zbl

[4] A. S. Shirkhorshidi, S. Aghabozorgi, T. Y. Wah, T. Herawan, “Big data clustering: A review”, Lecture Notes in Computer Science, 8583 (2014), 707–720 | DOI

[5] Alessio Farcomeni, Greco Luca, Robust methods for data reduction, CRC Press, Boca Raton, 2015, 297 pp. | Zbl

[6] Osborne, Jason W., Best practices in data cleaning: A complete quide to everything you need to do before and after collecting your data, SAGE Publication, Inc., Los Angeles, 2013, 296 pp.

[7] D. Aloise, A. Deshpande, P. Hansen, P. Popat, “NP-hardness of Euclidean sum-of-squares clustering”, Machine Learning, 75:2 (2009), 245–248 | DOI | Zbl

[8] Papadimitriou C. H., “Worst-case and probabilistic analysis of a geometric location problem”, SIAM J. Comput., 10:3 (1981), 542–557 | DOI | MR | Zbl

[9] Masuyama S., Ibaraki T., Hasegawa T., “The computational complexity of the m-center problems in the plane”, Trans. IECE Jpn., 64:2 (1981), 57–64

[10] Hatami B, Zarrabi-Zade H., “A streaming algorithm for 2-center with outliers in high dimensions”, Computational Geometry, 60 (2017), 26–36 | DOI | MR | Zbl

[11] Kelmanov A. V., Pyatkin A. V., “NP-trudnost nekotorykh evklidovykh zadach razbieniya konechnogo mnozhestva tochek”, Zhurn. vychisl. matematiki i mat. fiziki, 58:5 (2018), 852–856 | DOI | Zbl

[12] Garey M. R., Johnson D. S., Computers and intractability: A quide to the theory of NP-completeness, Freeman, San Francisco, 1979, 338 pp. | MR