Volume 21, No 3, 2014, P. 4152
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 NPhard 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 sumofsquared 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 sumofsquared distances, NPhardness, 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
email: kelm@math.nsc.ru, rsm@math.nsc.ru
