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

Alexander Kel'Manov, Vladimir Khandeev

Research output: Contribution to journalArticlepeer-review

Abstract

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.

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

Cite this