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

Abstract

We consider the 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 cluster elements and their centers. The centers of some clusters are given as input, while the other centers are defined as centroids (geometric centers). It is well known that the general case of the problem is strongly NP-hard. In this paper, we have shown that there exists an exact polynomial-time algorithm for the one-dimensional case of the problem.