Algorithms with performance guarantee for some quadratic euclidean problems of 2-partitioning a set and a sequence

Alexander Kel'Manov, Vladimir Khandeev

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


We consider the problems of 2-partitioning a finite set and a finite sequence of points in Euclidean space into clusters (subsets or subsequences) minimizing the sum of squared distances between cluster elements and the corresponding cluster centers. It is assumed that the center of one of the desired clusters is the origin, while the center of the other cluster is unknown and determined as the mean value over cluster elements. In this work, we present a short survey on some results for these problems and a new result: a randomized algorithm for the sequence partitioning problem.

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