Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space. / Kel’manov, Alexander; Pyatkin, Artem; Khamidullin, Sergey et al.
Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. p. 120-130 (Communications in Computer and Information Science; Vol. 871).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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 -
ID: 14464486