An Approximation Polynomial Algorithm for a Problem of Searching for the Longest Subsequence in a Finite Sequence of Points in Euclidean Space
| Autor: | Alexander Kel'manov, Sergey A. Khamidullin, V. I. Khandeev, V. V. Shenmaier, Yury V. Shamardin, Artem V. Pyatkin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Sequence
Euclidean space Centroid 02 engineering and technology Longest increasing subsequence 01 natural sciences 010309 optics Combinatorics Quadratic equation Bounded function 0103 physical sciences Euclidean geometry Subsequence 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Communications in Computer and Information Science ISBN: 9783319937991 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|