NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes

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

Abstract

We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research
Subtitle of host publicationRecent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers
EditorsAlexander Strekalovsky, Yury Kochetov, Tatiana Gruzdeva, Andrei Orlov
PublisherSpringer Science and Business Media Deutschland GmbH
Pages248-256
Number of pages9
ISBN (Print)9783030864323
DOIs
Publication statusPublished - 2021
Event20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021 - Virtual, Online
Duration: 5 Jul 202110 Jul 2021

Publication series

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

Conference

Conference20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021
CityVirtual, Online
Period05.07.202110.07.2021

Keywords

  • 2-clustering
  • Euclidean space
  • Mean
  • Medoid
  • Strong NP-hardness

OECD FOS+WOS

  • 1.01 MATHEMATICS
  • 1.02 COMPUTER AND INFORMATION SCIENCES

Fingerprint

Dive into the research topics of 'NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes'. Together they form a unique fingerprint.

Cite this