Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters

We consider the strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assume...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the Steklov Institute of Mathematics 2016-12, Vol.295 (Suppl 1), p.47-56
Main Authors: Dolgushev, A. V., Kel’manov, A. V., Shenmaier, V. V.
Format: Article
Language:English
Subjects:
Approximation
Clusters
Euclidean geometry
Euclidean space
Mathematical analysis
Mathematics
Mathematics and Statistics
Partitioning
Polynomials
Queuing theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is defined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.
ISSN:0081-5438
1531-8605
DOI:10.1134/S0081543816090066