Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence

Alexander Kel’manov, Sergey Khamidullin, Anna Panasenko

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

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

Аннотация

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
РедакторыNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
ИздательSpringer Gabler
Страницы135-145
Число страниц11
ISBN (печатное издание)9783030386283
DOI
СостояниеОпубликовано - 1 янв 2020
Событие13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Греция
Продолжительность: 27 мая 201931 мая 2019

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

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

Конференция

Конференция13th International Conference on Learning and Intelligent Optimization, LION 13
СтранаГреция
ГородChania
Период27.05.201931.05.2019

Fingerprint Подробные сведения о темах исследования «Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kel’manov, A., Khamidullin, S., & Panasenko, A. (2020). Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. В N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Ред.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (стр. 135-145). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_11