RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2015 Volume 21, Number 3, Pages 100–109 (Mi timm1202)

This article is cited in 19 papers

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

A. V. Dolgusheva, A. V. Kel'manovab, V. V. Shenmaierb

a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: 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 determined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.

Keywords: ptas, cluster analysis, euclidean space, $np$-hard problem, ptas.

UDC: 519.16+519.85

Received: 27.04.2015


 English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, 295, suppl. 1, 47–56

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024