Geodesic
On the complexity of the problem of choice of large clusters
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 136-143 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper considers the following problem. Given a set of Euclidean vectors, find several clusters with a restriction on the maximum scatter of each cluster so that the size of the minimum cluster would be maximum. Here the scatter is the sum of squared distances from the cluster elements to its centroid. The NP-hardness of this problem is proved in the case where the dimension of the space is a part of the input. Bibliogr. 15.
Keywords: cluster, scatter, NP-hardness.
Mots-clés : centroid 
@article{DA_2024_31_2_a7,
     author = {A. V. Pyatkin},
     title = {On the complexity of the problem of~choice~of~large~clusters},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {136--143},
     year = {2024},
     volume = {31},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_2_a7/}
}
TY  - JOUR
AU  - A. V. Pyatkin
TI  - On the complexity of the problem of choice of large clusters
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 136
EP  - 143
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_2_a7/
LA  - ru
ID  - DA_2024_31_2_a7
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%T On the complexity of the problem of choice of large clusters
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 136-143
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2024_31_2_a7/
%G ru
%F DA_2024_31_2_a7
A. V. Pyatkin. On the complexity of the problem of choice of large clusters. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 136-143. http://geodesic.mathdoc.fr/item/DA_2024_31_2_a7/

[1] Berkhin P., “A survey of clustering data mining techniques”, Grouping multidimensional data: Recent advances in clustering, Springer, Heidelberg, 2006, 25–71 | DOI

[2] Jain A. K., Dubes R. C., Algorithms for clustering data, Prentice Hall, Englewood Cliffs, NJ, 1988, 320 pp. | MR | Zbl

[3] Ghoreyshi S., Hosseinkhani J., “Developing a clustering model based on $K$-means algorithm in order to creating different policies for policyholders in insurance industry”, Int. J. Adv. Comput. Sci. Inf. Technol., 4:2 (2015), 46–53

[4] Fisher W. D., “On grouping for maximum homogeneity”, J. Am. Stat. Assoc., 53:284 (1958), 789–798 | DOI | MR | Zbl

[5] MacQueen J., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Mathematics, Statistics and Probability (Berkeley, USA, June 21 – July 18, 1965; Dec. 27, 1965 – Jan. 7, 1966), v. 1, Univ. Calif. Press, Berkeley, 1967, 281–297 | MR | Zbl

[6] Blömer J., Lammersen C., Schmidt M., Sohler C., “Theoretical analysis of the $k$-means algorithm — A survey”, Algorithm engineering: Selected results and surveys, Lect. Notes Comput. Sci., 9220, Springer, Cham, 2016, 81–116 | DOI | MR

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

[8] Pyatkin A. V., Aloise D., Mladenovic N., “NP-hardness of balanced minimum sum-of-squares clustering”, Pattern Recognit. Lett., 97 (2017), 44–45 | DOI

[9] Bertoni A., Goldwurm M., Lin J., Saccà F., “Size constrained distance clustering: Separation properties and some complexity results”, Fund. Inform., 115:1 (2012), 125–139 | DOI | MR | Zbl

[10] A. V. Kel'manov and A. V. Pyatkin, “NP-completeness of some problems of choosing a vector subset”, J. Appl. Ind. Math., 5:3 (2011), 352–357 | DOI | MR | Zbl

[11] A. V. Kel'manov, A. V. Pyatkin, and V. I. Khandeev, “On the complexity of some max-min clustering problems”, Proc. Steklov Inst. Math., 309, Suppl. 1 (2020), S65–S73 | DOI | DOI | MR

[12] Khandeev V. I., Neshchadim S. M., “Constant-factor approximation algorithms for some maximin multi-clustering problems”, Mathematical optimization theory and operations research, Proc. 22nd Int. Conf. (Yekaterinburg, Russia, July 2–8, 2023), Lect. Notes Comput. Sci., 13930, Springer, Cham, 2023, 85–100 | DOI | MR | Zbl

[13] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[14] Dailey D. P., “Uniqueness of colorability and colorability of planar $4$-regular graphs are NP-complete”, Discrete Math., 30:3 (1980), 289–293 | DOI | MR | Zbl

[15] A. V. Kel'manov and A. V. Pyatkin, “On a version of the problem of choosing a vector subset”, J. Appl. Ind. Math., 3:4 (2009), 447–455 | DOI | MR | Zbl