An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem

Alexander Kel'Manov, Anna Motkova

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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 сен 201722 сен 2017

Конференция

Конференция2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017
СтранаРоссийская Федерация
ГородNovosibirsk
Период18.09.201722.09.2017

Fingerprint Подробные сведения о темах исследования «An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать