On the Complexity of the Problem of Choice of Large Clusters | Sciact - Система учета научной деятельности ИМ СО РАН

On the Complexity of the Problem of Choice of Large Clusters Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2024, Том: 18, Номер: 2, Страницы: 312-315 Страниц : 4 DOI: 10.1134/S1990478924020121

Ключевые слова

cluster, centroid, scatter, NP-hardness

Авторы

Pyatkin A.V. ¹

Организации

1	Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090 Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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.

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

Пяткин А.В.
О сложности задачи выбора кластеров большого размера
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.113-119. DOI: 10.33048/daio.2024.31.787 РИНЦ

Поступила в редакцию:	8 нояб. 2023 г.
Принята к публикации:	22 дек. 2023 г.
Опубликована в печати:	15 авг. 2024 г.
Опубликована online:	15 авг. 2024 г.

Scopus:	2-s2.0-85201409000
РИНЦ:	68611707
OpenAlex:	W4401604095

Пока нет цитирований