О сложности задачи выбора кластеров большого размера Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 31, Number: 2, Pages: 113-119 Pages count : 7 DOI: 10.33048/daio.2024.31.787 | ||
| Tags | кластер, центроид, разброс, NP-трудность. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
Рассматривается задача выбора в данном множестве евклидовых векторов заданного числа кластеров с ограничением на максимальный разброс каждого кластера так, чтобы размер минимального из этих кластеров был максимальным. Под разбросом понимается сумма квадратов расстояний от элементов кластера до его центроида. Доказана NP-трудность этой задачи в случае, когда размерность пространства является частью входа.
Cite:
Пяткин А.В.
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ
Translated:
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
Dates:
| Submitted: | Nov 8, 2023 |
| Accepted: | Dec 22, 2023 |
| Published print: | May 30, 2024 |
| Published online: | May 30, 2024 |
Identifiers:
| Elibrary: | 68484583 |
Citing:
Пока нет цитирований