On the complexity of some quadratic Euclidean 2-clustering problems


如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).

作者简介

A. Kel’manov

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

编辑信件的主要联系方式.
Email: kelm@math.nsc.ru
俄罗斯联邦, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090

A. Pyatkin

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

Email: kelm@math.nsc.ru
俄罗斯联邦, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090

补充文件

附件文件
动作
1. JATS XML

版权所有 © Pleiades Publishing, Ltd., 2016