|
Diskretnyi Analiz i Issledovanie Operatsii, 2012, Volume 19, Issue 2, Pages 92–100
(Mi da685)
|
|
|
|
This article is cited in 31 scientific papers (total in 31 papers)
Approximation scheme for one problem of a vector subset choice
V. V. Shenmaier S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
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.
Received: 15.06.2011 Revised: 08.09.2011
Citation:
V. V. Shenmaier, “Approximation scheme for one problem of a vector subset choice”, Diskretn. Anal. Issled. Oper., 19:2 (2012), 92–100; J. Appl. Industr. Math., 6:3 (2012), 381–386
Linking options:
https://www.mathnet.ru/eng/da685 https://www.mathnet.ru/eng/da/v19/i2/p92
|
Statistics & downloads: |
Abstract page: | 386 | Full-text PDF : | 84 | References: | 43 | First page: | 3 |
|