Volume 21, No 3, 2014, P. 41-52
A. V. Kel’manov and S. M. Romanchenko
FPTAS for solving a problem of search for a vector subset
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.
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
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: firstname.lastname@example.org, email@example.com