The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

Alexander Kel’manov, Vladimir Khandeev

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

Аннотация

We consider a 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 one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical centers). It is known that in the general case this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
РедакторыIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
ИздательSpringer International Publishing AG
Страницы207-216
Число страниц10
ISBN (печатное издание)9783030333935
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

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

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

Конференция

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

Fingerprint Подробные сведения о темах исследования «The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kel’manov, A., & Khandeev, V. (2019). The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension. В I. Bykadorov, V. Strusevich, & T. Tchemisova (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers (стр. 207-216). (Communications in Computer and Information Science; Том 1090 CCIS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-33394-2_16