Volume 19, No 3, 2012, P. 27-38

UDC 519.2+621.391
A. V. Kel’manov, S. M. Romanchenko, S. A. Khamidullin
Approximation algorithms for some NP-hard problems of searching a vectors subsequence

Abstract:
Some NP-hard 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 2-approximation algorithms for these problems are presented.
Bibliogr. 11.

Keywords: searching a vectors subsequence, minimum sum-of-squared distances, clustering, NP-hardness, effective approximation algorithm.

Kel’manov Alexander Vasilyevich ^1,2
Romanchenko Semyon Mikhailovich ¹
Romanchenko Semyon 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, kham@math.nsc.ru