Standard

An Approximation Scheme for the Problem of Finding a Subsequence. / Kel’manov, A. V.; Romanchenko, S. M.; Khamidullin, S. A.

In: Numerical Analysis and Applications, Vol. 10, No. 4, 01.10.2017, p. 313-323.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel’manov, AV, Romanchenko, SM & Khamidullin, SA 2017, 'An Approximation Scheme for the Problem of Finding a Subsequence', Numerical Analysis and Applications, vol. 10, no. 4, pp. 313-323. https://doi.org/10.1134/S1995423917040036

APA

Kel’manov, A. V., Romanchenko, S. M., & Khamidullin, S. A. (2017). An Approximation Scheme for the Problem of Finding a Subsequence. Numerical Analysis and Applications, 10(4), 313-323. https://doi.org/10.1134/S1995423917040036

Vancouver

Kel’manov AV, Romanchenko SM, Khamidullin SA. An Approximation Scheme for the Problem of Finding a Subsequence. Numerical Analysis and Applications. 2017 Oct 1;10(4):313-323. doi: 10.1134/S1995423917040036

Author

Kel’manov, A. V. ; Romanchenko, S. M. ; Khamidullin, S. A. / An Approximation Scheme for the Problem of Finding a Subsequence. In: Numerical Analysis and Applications. 2017 ; Vol. 10, No. 4. pp. 313-323.

BibTeX

@article{d4bc5eba17cf43f397e6a034c41e3723,
title = "An Approximation Scheme for the Problem of Finding a Subsequence",
abstract = "We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is the 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.",
keywords = "Euclidean space, FPTAS, minimum sum of squared distances, NP-hardness, sequence",
author = "Kel{\textquoteright}manov, {A. V.} and Romanchenko, {S. M.} and Khamidullin, {S. A.}",
year = "2017",
month = oct,
day = "1",
doi = "10.1134/S1995423917040036",
language = "English",
volume = "10",
pages = "313--323",
journal = "Numerical Analysis and Applications",
issn = "1995-4239",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "4",

}

RIS

TY - JOUR

T1 - An Approximation Scheme for the Problem of Finding a Subsequence

AU - Kel’manov, A. V.

AU - Romanchenko, S. M.

AU - Khamidullin, S. A.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is the 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.

AB - We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is the 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.

KW - Euclidean space

KW - FPTAS

KW - minimum sum of squared distances

KW - NP-hardness

KW - sequence

UR - http://www.scopus.com/inward/record.url?scp=85042695119&partnerID=8YFLogxK

U2 - 10.1134/S1995423917040036

DO - 10.1134/S1995423917040036

M3 - Article

AN - SCOPUS:85042695119

VL - 10

SP - 313

EP - 323

JO - Numerical Analysis and Applications

JF - Numerical Analysis and Applications

SN - 1995-4239

IS - 4

ER -

ID: 10342626