An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin

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

Аннотация

A problem of partitioning a finite sequence of points in Euclidean space into two subsequences (clusters) maximizing the size of the first cluster subject to two constraints is considered. The first constraint deals with every two consecutive indices of elements of the first cluster: the difference between them is bounded from above and below by some constants. The second one restricts the value of a quadratic clustering function that is the sum of the intracluster sums over both clusters. The intracluster sum is the sum of squared distances between cluster elements and the cluster center. The center of the first cluster is unknown and determined as the centroid (i.e. as the mean value of its elements), while the center of the second one is zero. The strong NP-hardness of the problem is shown and an exact algorithm is suggested for the case of integer coordinates of input points. If the space dimension is bounded by some constant this algorithm runs in a pseudopolynomial time.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
РедакторыYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
ИздательSpringer-Verlag GmbH and Co. KG
Страницы131-143
Число страниц13
ISBN (печатное издание)9783030109332
DOI
СостояниеОпубликовано - 1 янв 2019
Событие9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Черногория
Продолжительность: 1 окт 20185 окт 2018

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

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

Конференция

Конференция9th International Conference on Optimization and Applications, OPTIMA 2018
СтранаЧерногория
ГородPetrovac
Период01.10.201805.10.2018

    Fingerprint

Цитировать

Kel’manov, A., Khamidullin, S., Khandeev, V., & Pyatkin, A. (2019). An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. В Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Ред.), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (стр. 131-143). (Communications in Computer and Information Science; Том 974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-10934-9_10