NP-hardness of some max-min clustering problems

Alexander Kel’manov, Vladimir Khandeev, Artem Pyatkin

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

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
РедакторыYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
ИздательSpringer-Verlag GmbH and Co. KG
Страницы144-154
Число страниц11
ISBN (печатное издание)9783030109332
DOI
СостояниеОпубликовано - 1 янв 2019
Событие9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Черногория
Продолжительность: 1 окт 20185 окт 2018

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

НазваниеCommunications in Computer and Information Science
Том974
ISSN (печатное издание)1865-0929

Конференция

Конференция9th International Conference on Optimization and Applications, OPTIMA 2018
СтранаЧерногория
ГородPetrovac
Период01.10.201805.10.2018

Fingerprint

Подробные сведения о темах исследования «NP-hardness of some max-min clustering problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать