An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities

A. V. Kel’manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev

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

Аннотация

We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances of elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is the origin, while the centers of the other clusters are unknown and are defined as the mean values of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is lower and upper bounded by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.

Язык оригиналаанглийский
Страницы (с-по)88-96
Число страниц9
ЖурналProceedings of the Steklov Institute of Mathematics
Том299
DOI
СостояниеОпубликовано - 1 дек 2017

Fingerprint Подробные сведения о темах исследования «An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать