Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem

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

Аннотация

We consider a strongly NP-hard problem of clustering a finite set of points in Euclidean space into two clusters. In this problem, we find a partition of the input set 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 weight factors are the cardinalities of the corresponding clusters and the centers are defined as follows. The center of the first cluster is unknown and determined as the centroid, while the center of the other one is given as input (is the origin without loss of generality). In this paper, we present a polynomial-time exact algorithm for the one-dimensional case of the problem.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers
РедакторыYury Kochetov, Igor Bykadorov, Tatiana Gruzdeva
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы30-35
Число страниц6
ISBN (печатное издание)9783030586560
DOI
СостояниеОпубликовано - июл 2020
Событие19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020 - Novosibirsk, Российская Федерация
Продолжительность: 6 июл 202010 июл 2020

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

НазваниеCommunications in Computer and Information Science
Том1275 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020
СтранаРоссийская Федерация
ГородNovosibirsk
Период06.07.202010.07.2020

Fingerprint Подробные сведения о темах исследования «Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать