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

A. V. Kel’manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, Yu V. Shamardin, V. V. Shenmaier

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)363-370
Число страниц8
ЖурналPattern Recognition and Image Analysis
Том28
Номер выпуска3
DOI
СостояниеОпубликовано - 1 июл 2018

Fingerprint Подробные сведения о темах исследования «A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать