A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements

Standard

A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements. / Kel’manov, A. V.; Khamidullin, S. A.; Khandeev, V. I. et al.

In: Pattern Recognition and Image Analysis, Vol. 28, No. 3, 01.07.2018, p. 363-370.

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

BibTeX

@article{b18f137c971645c88a395a5526ba0252,

title = "A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements",

abstract = "We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M* of the optimal subsequence is even, or it yields a 12(1−1M*)-approximate solution if M* is odd. The time complexity of the algorithm is O(N3(N2+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.",

keywords = "Euclidean space, longest subsequence, NP-hard problem, polynomial-time approximation algorithm, quadratic scatter, similar elements, time-series analysis",

author = "Kel{\textquoteright}manov, {A. V.} and Khamidullin, {S. A.} and Khandeev, {V. I.} and Pyatkin, {A. V.} and Shamardin, {Yu V.} and Shenmaier, {V. V.}",

note = "Publisher Copyright: {\textcopyright} 2018, Pleiades Publishing, Ltd.",

year = "2018",

month = jul,

day = "1",

doi = "10.1134/S1054661818030094",

language = "English",

volume = "28",

pages = "363--370",

journal = "Pattern Recognition and Image Analysis",

issn = "1054-6618",

publisher = "Maik Nauka Publishing / Springer SBM",

number = "3",

}

RIS

TY - JOUR

T1 - A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements

AU - Kel’manov, A. V.

AU - Khamidullin, S. A.

AU - Khandeev, V. I.

AU - Pyatkin, A. V.

AU - Shamardin, Yu V.

AU - Shenmaier, V. V.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M* of the optimal subsequence is even, or it yields a 12(1−1M*)-approximate solution if M* is odd. The time complexity of the algorithm is O(N3(N2+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.

AB - We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M* of the optimal subsequence is even, or it yields a 12(1−1M*)-approximate solution if M* is odd. The time complexity of the algorithm is O(N3(N2+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.

KW - Euclidean space

KW - longest subsequence

KW - NP-hard problem

KW - polynomial-time approximation algorithm

KW - quadratic scatter

KW - similar elements

KW - time-series analysis

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

U2 - 10.1134/S1054661818030094

DO - 10.1134/S1054661818030094

M3 - Article

AN - SCOPUS:85053480541

VL - 28

SP - 363

EP - 370

JO - Pattern Recognition and Image Analysis

JF - Pattern Recognition and Image Analysis

SN - 1054-6618

IS - 3

ER -

ID: 16601993