Volume 19, No 3, 2012, P. 2738
UDC 519.2+621.391
A. V. Kel’manov, S. M. Romanchenko, S. A. Khamidullin
Approximation algorithms for some NPhard problems of searching a vectors subsequence
Abstract:
Some NPhard problems of searching a subsequence in a finite sequence of Euclidean vectors are studied. It is assumed that the desired subsequence has a fixed number of vectors which are mutually close under the criterion of minimum sum of squared distances. Moreover, there is an additional requirement that the difference between the numbers of any two consecutive vectors must lie between two given constants. Some effective 2approximation algorithms for these problems are presented.
Bibliogr. 11.
Keywords: searching a vectors subsequence, minimum sumofsquared distances, clustering, NPhardness, effective approximation algorithm.
Kel’manov Alexander Vasilyevich ^{1,2}
Romanchenko Semyon Mikhailovich ^{1}
Romanchenko Semyon Mikhailovich ^{1}
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, kham@math.nsc.ru
