TY - GEN

T1 - The Problem K-Means and Given J-Centers

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

AU - Kel’manov, Alexander

AU - Khandeev, Vladimir

PY - 2019/1/1

Y1 - 2019/1/1

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

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

KW - Euclidean space

KW - Minimum sum-of-squares clustering

KW - One-dimensional case

KW - Polynomial-time algorithm

KW - Strongly NP-hard problem

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

U2 - 10.1007/978-3-030-33394-2_16

DO - 10.1007/978-3-030-33394-2_16

M3 - Conference contribution

AN - SCOPUS:85076160194

SN - 9783030333935

T3 - Communications in Computer and Information Science

SP - 207

EP - 216

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers

A2 - Bykadorov, Igor

A2 - Strusevich, Vitaly

A2 - Tchemisova, Tatiana

PB - Springer International Publishing AG

Y2 - 8 July 2019 through 12 July 2019

ER -