TY - JOUR

T1 - Algorithms with performance guarantee for a weighted 2-partition problem

AU - Kel'Manov, Alexander

AU - Motkova, Anna

N1 - Publisher Copyright: © Copyright by the paper's authors.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85036616068&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85036616068

VL - 1987

SP - 304

EP - 309

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

SN - 1613-0073

ER -