On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters

Alexander Kel’manov, Vladimir Khandeev, Artem Pyatkin

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

Аннотация

We consider three problems of partitioning a finite set of N points in the d-dimensional Euclidean space into two clusters balancing the value of (1) the normalized by a cluster size sum of squared deviations from the mean, (2) the sum of squared deviations from the mean, and (3) the size-weighted sum of squared deviations from the mean. We have proved the NP-completeness of all these problems.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
РедакторыMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
ИздательSpringer Gabler
Страницы127-136
Число страниц10
ISBN (печатное издание)9783030386023
DOI
СостояниеОпубликовано - 1 янв 2020
Событие10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Черногория
Продолжительность: 30 сен 20194 окт 2019

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

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

Конференция

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

Fingerprint Подробные сведения о темах исследования «On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать