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

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

Original languageEnglish
Pages (from-to)339-342
Number of pages4
JournalDoklady Mathematics
Volume100
Issue number1
DOIs
Publication statusPublished - 1 Jul 2019

Fingerprint

Dive into the research topics of 'On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line'. Together they form a unique fingerprint.

Cite this