@inproceedings{c7ee023902f24abb9f153c471ea476ab,

title = "On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line",

abstract = "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.",

keywords = "Euclidean space, Minimum Sum-of-Squares Clustering, NP-hard problem, One-dimensional case, Polynomial solvability",

author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev",

year = "2020",

month = jan,

day = "22",

doi = "10.1007/978-3-030-38629-0_4",

language = "English",

isbn = "9783030386283",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Gabler",

pages = "46--52",

editor = "Matsatsinis, {Nikolaos F.} and Yannis Marinakis and Panos Pardalos",

booktitle = "Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers",

address = "Germany",

note = "13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",

}