О сложности двух задач поиска кластеров с большой мощностью Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 32, Number: 4, Pages: 172–190 Pages count : 20 DOI: 10.33048/daio.2025.32.834 | ||||
| Tags | Кластеризация, NP-полнота, Евклидово пространство, Ограниченный разброс, Наименьший размер кластера. | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0015 |
Abstract:
В работе рассматриваются задачи поиска в конечном множестве точек евклидова пространства непересекающихся подмножеств. В одной из задач мощность каждого из подмножеств должна быть не меньше заданного числа. В другой задаче мощность всех подмножеств должна быть одинакова, и в объединении они должны совпадать со всем исходным множеством. В обеих задачах дополнительно требуется, чтобы для каждого подмножества сумма квадратов расстояний до центроида не превосходила заданной величины. Доказано, что задачи NP-полны в сильном смысле в случае, когда число кластеров равно двум, а размерность пространства является частью входа задачи. Кроме того, доказано, что задачи NP-полны в одномерном случае для любого фиксированного числа кластеров.
Cite:
Нещадим С.М.
, Хандеев В.И.
О сложности двух задач поиска кластеров с большой мощностью
Дискретный анализ и исследование операций. 2025. Т.32. №4. С.172–190. DOI: 10.33048/daio.2025.32.834
О сложности двух задач поиска кластеров с большой мощностью
Дискретный анализ и исследование операций. 2025. Т.32. №4. С.172–190. DOI: 10.33048/daio.2025.32.834
Dates:
| Submitted: | May 5, 2025 |
| Accepted: | Sep 22, 2025 |
| Published print: | Jun 4, 2026 |
| Published online: | Jun 4, 2026 |
Identifiers:
No identifiers