The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

Alexander Kel’manov, Vladimir Khandeev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
EditorsIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
PublisherSpringer International Publishing AG
Pages207-216
Number of pages10
ISBN (Print)9783030333935
DOIs
Publication statusPublished - 1 Jan 2019
Event18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation
Duration: 8 Jul 201912 Jul 2019

Publication series

NameCommunications in Computer and Information Science
Volume1090 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
CountryRussian Federation
CityEkaterinburg
Period08.07.201912.07.2019

Keywords

  • Euclidean space
  • Minimum sum-of-squares clustering
  • One-dimensional case
  • Polynomial-time algorithm
  • Strongly NP-hard problem

Fingerprint Dive into the research topics of 'The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension'. Together they form a unique fingerprint.

Cite this