Volume 18, No 1, 2011, P. 6169
UDC 519.2+621.391
A. V. Kel'manov, S. M. Romanchenko
The approximation algorithm for one problem of searching for subset of vectors
Abstract:
One problem in data analysis was earlier reduced to the specific NPhard optimization problem. In this problem one needs to find a subset of given set of Euclidean vectors satisfying the following conditions. Firstly the required subset must have the given cardinality and secondly it should include vectors which are mutually close under the criterion of minimum sum of squared distances. In the paper, an effective 2approximation algorithm for this problem is proved.
Bibliogr. 3.
Keywords: searching for subset of vectors, NPhardness, effective approximation algorithm.
Kel’manov Alexander Vasilyevich ^{1,2}
Romanchenko Semjon Mikhailovich ^{2}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: kelm@math.nsc.ru, semenr@bk.ru
