2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence

Alexander Kel’manov, Sergey Khamidullin, Anna Panasenko

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

Аннотация

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. 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 some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.

Язык оригиналаанглийский
Название основной публикацииNumerical Computations
Подзаголовок основной публикацииTheory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers
РедакторыYaroslav D. Sergeyev, Dmitri E. Kvasov
ИздательSpringer Gabler
Страницы386-393
Число страниц8
ISBN (печатное издание)9783030406158
DOI
СостояниеОпубликовано - 1 янв 2020
Событие3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 - Crotone, Италия
Продолжительность: 15 июн 201921 июн 2019

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

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

Конференция

Конференция3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
СтранаИталия
ГородCrotone
Период15.06.201921.06.2019

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

  • Цитировать

    Kel’manov, A., Khamidullin, S., & Panasenko, A. (2020). 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence. В Y. D. Sergeyev, & D. E. Kvasov (Ред.), Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers (стр. 386-393). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11974 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-40616-5_34