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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research
Подзаголовок основной публикацииRecent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers
РедакторыAlexander Strekalovsky, Yury Kochetov, Tatiana Gruzdeva, Andrei Orlov
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы248-256
Число страниц9
ISBN (печатное издание)9783030864323
DOI
СостояниеОпубликовано - 2021
Событие20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021 - Virtual, Online
Продолжительность: 5 июл 202110 июл 2021

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1476 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021
ГородVirtual, Online
Период05.07.202110.07.2021

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА
  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ

Fingerprint

Подробные сведения о темах исследования «NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать