Algorithms with performance guarantee for a weighted 2-partition problem

Alexander Kel'Manov, Anna Motkova

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)304-309
Number of pages6
JournalCEUR Workshop Proceedings
Volume1987
Publication statusPublished - 2017

Fingerprint

Dive into the research topics of 'Algorithms with performance guarantee for a weighted 2-partition problem'. Together they form a unique fingerprint.

Cite this