RUS  ENG
Full version
JOURNALS // Sibirskii Zhurnal Vychislitel'noi Matematiki // Archive

Sib. Zh. Vychisl. Mat., 2017 Volume 20, Number 4, Pages 379–392 (Mi sjvm658)

This article is cited in 5 papers

An approximation scheme for a problem of finding a subsequence

A. V. Kelmanovab, S. M. Romanchenkoa, S. A. Khamidullina

a Sobolev Institute of Mathematics SB RAS, 4 Acad. Koptyug av., Novosibirsk, 630090, Russia
b Novosibirsk State University, 2 Pirogova str., Novosibirsk, 630090, Russia

Abstract: We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is a minimum sum of squared distances from the elements of a sought subsequence to its geometric center (centroid). It is assumed that a sought subsequence contains a given number of elements. In addition, a sought subsequence should satisfy the following condition: the difference between the indices of each previous and subsequent points is bounded with given lower and upper constants. We present an approximation algorithm of solving the problem and prove that it is a fully polynomial-time approximation scheme (FPTAS) when the space dimension is bounded by a constant.

Key words: euclidean space, sequence, minimum sum of squared distances, NP-hardness, FPTAS.

UDC: 519.2+621.391

Received: 01.09.2016
Revised: 08.01.2017

DOI: 10.15372/SJNM20170403


 English version:
Numerical Analysis and Applications, 2017, 10:4, 313–323

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024