Volume 21, No 3, 2014, P. 41-52

UDC 519.16+519.85
A. V. Kel’manov and S. M. Romanchenko
FPTAS for solving a problem of search for a vector subset

Abstract:
We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P=NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented.
Bibliogr. 12.

Keywords: search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.

Kel’manov Alexander Vasilievich ^1,2
Romanchenko Semеn Mikhailovich ^1,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
e-mail: kelm@math.nsc.ru, rsm@math.nsc.ru