Algorithms with performance guarantee for a weighted 2-partition problem

Alexander Kel'Manov, Anna Motkova

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование


We consider the problem of partitioning a finite set of Euclidean points into two clusters minimizing the sum over both clusters the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are the cardinalities of the corresponding clusters. In this work, we present a short survey on the results for this problem and a new result: a 2-approximation algorithm.

Язык оригиналаанглийский
Страницы (с-по)304-309
Число страниц6
ЖурналCEUR Workshop Proceedings
СостояниеОпубликовано - 2017


Подробные сведения о темах исследования «Algorithms with performance guarantee for a weighted 2-partition problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).