A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem

Alexander Kel’manov, Anna Motkova

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

16 Цитирования (Scopus)

Аннотация

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the geometric center (centroid), i.e. the average value over all points in the cluster. We analyze the variant of the problem with cardinality constraints. We present an approximation algorithm for the problem and prove that it is a fully polynomial-time approximation scheme when the space dimension is bounded by a constant.

Язык оригиналаанглийский
Название основной публикацииDiscrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov, Vladimir Beresnev, Evgeni Nurminski
ИздательSpringer-Verlag GmbH and Co. KG
Страницы182-192
Число страниц11
ISBN (печатное издание)9783319449135
DOI
СостояниеОпубликовано - 2016
Событие9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 - Vladivostok, Российская Федерация
Продолжительность: 19 сен 201623 сен 2016

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

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9869 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
СтранаРоссийская Федерация
ГородVladivostok
Период19.09.201623.09.2016

Fingerprint Подробные сведения о темах исследования «A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать