Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem

A. V. Kel’manov, V. I. Khandeev

Research output: Contribution to journalArticlepeer-review


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 of the clusters are given as an input, while the centers of the others are determined as centroids (geometric 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.

Original languageEnglish
Pages (from-to)1553-1561
Number of pages9
JournalComputational Mathematics and Mathematical Physics
Issue number9
Publication statusPublished - 1 Sep 2019


  • clustering
  • Euclidean space
  • minimum sum-of-squares
  • one-dimensional case
  • partitioning
  • polynomial-time solvability
  • strongly NP-hard problem


Dive into the research topics of 'Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem'. Together they form a unique fingerprint.

Cite this