Randomized algorithms for some sequence clustering problems

Sergey Khamidullin, Vladimir Khandeev, Anna Panasenko

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

Аннотация

We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers
РедакторыIlias S. Kotsireas, Panos M. Pardalos
ИздательSpringer Gabler
Страницы96-101
Число страниц6
ISBN (печатное издание)9783030535513
DOI
СостояниеОпубликовано - 1 июн 2020
Событие14th International Conference on Learning and Intelligent Optimization, LION 2020 - Athens, Греция
Продолжительность: 24 мая 202028 мая 2020

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

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12096 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция14th International Conference on Learning and Intelligent Optimization, LION 2020
СтранаГреция
ГородAthens
Период24.05.202028.05.2020

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

  • Цитировать

    Khamidullin, S., Khandeev, V., & Panasenko, A. (2020). Randomized algorithms for some sequence clustering problems. В I. S. Kotsireas, & P. M. Pardalos (Ред.), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers (стр. 96-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12096 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-53552-0_11