TY - GEN

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

AU - Kel’manov, Alexander

AU - Khandeev, Vladimir

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/22

Y1 - 2020/1/22

N2 - 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.

AB - 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.

KW - Euclidean space

KW - Minimum Sum-of-Squares Clustering

KW - NP-hard problem

KW - One-dimensional case

KW - Polynomial solvability

UR - http://www.scopus.com/inward/record.url?scp=85082389518&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38629-0_4

DO - 10.1007/978-3-030-38629-0_4

M3 - Conference contribution

AN - SCOPUS:85082389518

SN - 9783030386283

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 46

EP - 52

BT - Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers

A2 - Matsatsinis, Nikolaos F.

A2 - Marinakis, Yannis

A2 - Pardalos, Panos

PB - Springer Gabler

T2 - 13th International Conference on Learning and Intelligent Optimization, LION 13

Y2 - 27 May 2019 through 31 May 2019

ER -