Volume 19, No 2, 2012, P. 93-101

UDC 519.176
V. V. Shenmaier 
Approximation scheme for one problem of a vector subset choice

Abstract:
We consider the following clustering problem: in a given vector set to find a vector subset of cardinality $k$ with the minimal quadratic deviation from its mean. The distances between vectors are defined by the Euclidean metric. We propose an approximation scheme (PTAS) that solves this problem with an arbitrary relative error $\varepsilon$ in time $O(n^{2/\varepsilon+1}(9/\varepsilon)^{3/\varepsilon d})$, where $n$ is the number of vectors in the original set and $d$ is the space dimension.
Ill. 1, bibliogr. 4.

Keywords: vector subset choice, cluster analysis, approximation scheme, approximation algorithm.

Shenmaier Vladimir Vladimirovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru