Randomized algorithms for some clustering problems

Alexander Kel’manov, Vladimir Khandeev, Anna Panasenko

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

8 Цитирования (Scopus)


We consider two strongly NP-hard problems of clustering a finite set of points in Euclidean Space. Both problems have applications, in particular, in data analysis, data mining, pattern recognition, and machine learning. In the first problem, an input set is given and we need to find a cluster (i.e., a subset) of a given size which minimizes the sum of squared distances between the elements of this cluster and its centroid (the geometric center). Every point outside this cluster is considered as singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first cluster is unknown and determined as the centroid, while the center of the second one is the origin. The weight factors for both intracluster sums are the given clusters sizes. In this paper, we present parameterized randomized algorithms for these problems. For given upper bounds of the relative error and failure probability, the parameter value is defined for which both our algorithms find approximate solutions in a polynomial time. This running time is linear on the space dimension and on the input set size. The conditions are found under which these algorithms are asymptotically exact and have the time complexity that is linear on the space dimension and quadratic on the size of the input set.

Язык оригиналаанглийский
Название основной публикацииOptimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Число страниц11
ISBN (печатное издание)9783319937991
СостояниеОпубликовано - 1 янв. 2018
Событие7th International Conference on Optimization Problems and Their Applications, OPTA 2018 - Omsk, Российская Федерация
Продолжительность: 8 июн. 201814 июн. 2018

Серия публикаций

НазваниеCommunications in Computer and Information Science
ISSN (печатное издание)1865-0929


Конференция7th International Conference on Optimization Problems and Their Applications, OPTA 2018
Страна/TерриторияРоссийская Федерация


Подробные сведения о темах исследования «Randomized algorithms for some clustering problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).