TY - GEN

T1 - An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space

AU - Kel’manov, Alexander

AU - Pyatkin, Artem

AU - Khamidullin, Sergey

AU - Khandeev, Vladimir

AU - Shamardin, Yury V.

AU - Shenmaier, Vladimir

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The following problem is considered. Given a finite sequence of Euclidean points, find a subsequence of the longest length (size) such that the sum of squared distances between the elements of this subsequence and its unknown centroid (geometrical center) is at most a given percentage of the sum of squared distances between the elements of the input sequence and its centroid. This problem models, in particular, one of the data analysis problems, namely, search for the maximum subset of elements close to each other in the sense of the bounded from above the total quadratic scatter in the set of time-ordered data. It can be treated as a data editing problem aimed at the removal of extraneous (dissimilar) elements. It is shown that the problem is strongly NP-hard. A polynomial time approximation algorithm is proposed. It either finds out that the problem has no solutions or outputs a 1/2-approximate solution if the length M* of an optimal subsequence is even, or it outputs a (M* - 1)/2M* -approximate solution if M* is odd. Some examples of numerical experiments illustrating the algorithm suitability are presented.

AB - The following problem is considered. Given a finite sequence of Euclidean points, find a subsequence of the longest length (size) such that the sum of squared distances between the elements of this subsequence and its unknown centroid (geometrical center) is at most a given percentage of the sum of squared distances between the elements of the input sequence and its centroid. This problem models, in particular, one of the data analysis problems, namely, search for the maximum subset of elements close to each other in the sense of the bounded from above the total quadratic scatter in the set of time-ordered data. It can be treated as a data editing problem aimed at the removal of extraneous (dissimilar) elements. It is shown that the problem is strongly NP-hard. A polynomial time approximation algorithm is proposed. It either finds out that the problem has no solutions or outputs a 1/2-approximate solution if the length M* of an optimal subsequence is even, or it outputs a (M* - 1)/2M* -approximate solution if M* is odd. Some examples of numerical experiments illustrating the algorithm suitability are presented.

KW - Euclidean space

KW - Longest subsequence

KW - NP-hard problem

KW - Polynomial-time approximation algorithm

KW - Quadratic variation

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

U2 - 10.1007/978-3-319-93800-4_10

DO - 10.1007/978-3-319-93800-4_10

M3 - Conference contribution

AN - SCOPUS:85049671805

SN - 9783319937991

T3 - Communications in Computer and Information Science

SP - 120

EP - 130

BT - Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 7th International Conference on Optimization Problems and Their Applications, OPTA 2018

Y2 - 8 June 2018 through 14 June 2018

ER -