An approximation scheme for a weighted two-cluster partition problem

Alexander Kel’manov, Anna Motkova, Vladimir Shenmaier

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

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


We consider the problem of partitioning a set of Euclidean points into two clusters to minimize the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are given as input. We present an approximation algorithm for the problem, which is based on an adaptive-grid-approach. The algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of the fixed space dimension. In the case when the dimension of space is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
РедакторыWMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
ИздательSpringer-Verlag GmbH and Co. KG
Число страниц11
ISBN (печатное издание)9783319730127
СостояниеОпубликовано - 1 янв. 2018
Событие6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Российская Федерация
Продолжительность: 27 июл. 201729 июл. 2017

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

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


Конференция6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Страна/TерриторияРоссийская Федерация


Подробные сведения о темах исследования «An approximation scheme for a weighted two-cluster partition problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).