Аннотация
We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum over both clusters of the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster. The variant of the problem in which the cardinalities of the clusters are parts of the input is analyzed. We present and prove a 2-approximation polynomial-time algorithm for this problem.
Язык оригинала | английский |
---|---|
Название основной публикации | Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 |
Издатель | Institute of Electrical and Electronics Engineers Inc. |
Страницы | 94-96 |
Число страниц | 3 |
ISBN (электронное издание) | 9781538615966 |
DOI | |
Состояние | Опубликовано - 14 ноя 2017 |
Событие | 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 - Novosibirsk, Российская Федерация Продолжительность: 18 сен 2017 → 22 сен 2017 |
Конференция
Конференция | 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 |
---|---|
Страна | Российская Федерация |
Город | Novosibirsk |
Период | 18.09.2017 → 22.09.2017 |