Volume 18, No 1, 2011, P. 61-69

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 NP-hard 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 2-approximation algorithm for this problem is proved.
Bibliogr. 3.

Keywords: searching for subset of vectors, NP-hardness, effective approximation algorithm.

Kel’manov Alexander Vasilyevich ^1,2
Romanchenko Semjon Mikhailovich ²
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
e-mail: kelm@math.nsc.ru, semenr@bk.ru