On the Complexity of the Problem of Choice of Large Clusters Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 18, Number: 2, Pages: 312-315 Pages count : 4 DOI: 10.1134/S1990478924020121 | ||
| Tags | cluster, centroid, scatter, NP-hardness | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
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 part of the input.
Cite:
Pyatkin A.V.
On the Complexity of the Problem of Choice of Large Clusters
Journal of Applied and Industrial Mathematics. 2024. V.18. N2. P.312-315. DOI: 10.1134/S1990478924020121 Scopus РИНЦ OpenAlex
On the Complexity of the Problem of Choice of Large Clusters
Journal of Applied and Industrial Mathematics. 2024. V.18. N2. P.312-315. DOI: 10.1134/S1990478924020121 Scopus РИНЦ OpenAlex
Original:
Пяткин А.В.
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ
Dates:
| Submitted: | Nov 8, 2023 |
| Accepted: | Dec 22, 2023 |
| Published print: | Aug 15, 2024 |
| Published online: | Aug 15, 2024 |
Identifiers:
| Scopus: | 2-s2.0-85201409000 |
| Elibrary: | 68611707 |
| OpenAlex: | W4401604095 |
Citing:
Пока нет цитирований