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

Alexander Kel’manov, Vladimir Khandeev

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

Abstract

We consider one 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 some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

Original languageEnglish
Title of host publicationLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
EditorsNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
PublisherSpringer Gabler
Pages46-52
Number of pages7
ISBN (Print)9783030386283
DOIs
Publication statusPublished - 22 Jan 2020
Event13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Greece
Duration: 27 May 201931 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11968 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Learning and Intelligent Optimization, LION 13
CountryGreece
CityChania
Period27.05.201931.05.2019

Keywords

  • Euclidean space
  • Minimum Sum-of-Squares Clustering
  • NP-hard problem
  • One-dimensional case
  • Polynomial solvability

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