Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem


Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

We consider the strongly NP-hard problem of partitioning a finite set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sums of the squared intra-cluster distances from the elements of the cluster to its center. The weights of the sums are equal to 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 is determined as the mean value over all points in this cluster, i.e., as the geometric center (centroid). The version of the problem with constrained cardinalities of the clusters is analyzed. We construct an approximation algorithm for the problem and show that it is a fully polynomial-time approximation scheme (FPTAS) if the space dimension is bounded by a constant.

Авторлар туралы

A. Kel’manov

Sobolev Institute of Mathematics; Novosibirsk State University

Хат алмасуға жауапты Автор.
Email: kelm@math.nsc.ru
Ресей, pr. Akad. Koptyuga 4, Novosibirsk; ul. Pirogova 2, Novosibirsk

A. Motkova

Sobolev Institute of Mathematics; Novosibirsk State University

Email: kelm@math.nsc.ru
Ресей, pr. Akad. Koptyuga 4, Novosibirsk; ul. Pirogova 2, Novosibirsk

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML

© Pleiades Publishing, Ltd., 2018