NP-hardness of some max-min clustering problems

Alexander Kel’manov, Vladimir Khandeev, Artem Pyatkin

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


We consider some consimilar problems of searching for disjoint clusters in the finite set of points in Euclidean space. The goal is to maximize the minimum subset size so that the value of each intracluster quadratic variation would not exceed a given constant. We prove that all considered problems are NP-hard even on a line.

Original languageEnglish
Title of host publicationOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
EditorsYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
PublisherSpringer-Verlag GmbH and Co. KG
Number of pages11
ISBN (Print)9783030109332
Publication statusPublished - 1 Jan 2019
Event9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Montenegro
Duration: 1 Oct 20185 Oct 2018

Publication series

NameCommunications in Computer and Information Science
ISSN (Print)1865-0929


Conference9th International Conference on Optimization and Applications, OPTIMA 2018


  • Clustering
  • Euclidean space
  • Max-Min problem
  • NP-hardness
  • Quadratic variation

Fingerprint Dive into the research topics of 'NP-hardness of some max-min clustering problems'. Together they form a unique fingerprint.

Cite this