1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation Научная публикация
| Журнал |
Yugoslav Journal of Operations Research
ISSN: 0354-0243 , E-ISSN: 2334-6043 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2023, Том: 33, Номер: 1, Страницы: 59-69 Страниц : 11 DOI: 10.2298/yjor211018008p | ||||
| Ключевые слова | Euclidean space, mean, medoid, 2-clustering, 2-approximation algorithm, strong NP-hardness. | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | 0314-2019-0014 |
| 2 | Российский фонд фундаментальных исследований | 19-01-00308 |
Реферат:
We consider the following 2-clustering problem. Given N points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the problem remains NP-hard in the case of arbitrary clust/
Библиографическая ссылка:
Pyatkin A.V.
1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation
Yugoslav Journal of Operations Research. 2023. V.33. N1. P.59-69. DOI: 10.2298/yjor211018008p Scopus РИНЦ OpenAlex
1-mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation
Yugoslav Journal of Operations Research. 2023. V.33. N1. P.59-69. DOI: 10.2298/yjor211018008p Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 14 окт. 2021 г. |
| Принята к публикации: | 14 апр. 2022 г. |
| Опубликована online: | 27 сент. 2022 г. |
| Опубликована в печати: | 15 февр. 2023 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85149693690 |
| РИНЦ: | 60074979 |
| OpenAlex: | W4285269600 |