On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line

Alexander Kel’manov, Vladimir Khandeev

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

Аннотация

We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
РедакторыNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
ИздательSpringer Gabler
Страницы46-52
Число страниц7
ISBN (печатное издание)9783030386283
DOI
СостояниеОпубликовано - 22 янв 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

Цитировать

Kel’manov, A., & Khandeev, V. (2020). On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. В N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Ред.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (стр. 46-52). (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_4