Standard

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 и др.

Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. стр. 120-130 (Communications in Computer and Information Science; Том 871).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаяРецензирование

Harvard

Kel’manov, A, Pyatkin, A, Khamidullin, S, Khandeev, V, Shamardin, YV & Shenmaier, V 2018, An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space. в Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Communications in Computer and Information Science, Том. 871, Springer-Verlag GmbH and Co. KG, стр. 120-130, 7th International Conference on Optimization Problems and Their Applications, OPTA 2018, Omsk, Российская Федерация, 08.06.2018. https://doi.org/10.1007/978-3-319-93800-4_10

APA

Kel’manov, A., Pyatkin, A., Khamidullin, S., Khandeev, V., Shamardin, Y. V., & Shenmaier, V. (2018). An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space. в Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers (стр. 120-130). (Communications in Computer and Information Science; Том 871). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-93800-4_10

Vancouver

Kel’manov A, Pyatkin A, Khamidullin S, Khandeev V, Shamardin YV, Shenmaier V. An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space. в Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. стр. 120-130. (Communications in Computer and Information Science). doi: 10.1007/978-3-319-93800-4_10

Author

Kel’manov, Alexander ; Pyatkin, Artem ; Khamidullin, Sergey и др. / An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space. Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. стр. 120-130 (Communications in Computer and Information Science).

BibTeX

@inproceedings{b686987904c9428889ed2350a35160fc,
title = "An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space",
abstract = "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.",
keywords = "Euclidean space, Longest subsequence, NP-hard problem, Polynomial-time approximation algorithm, Quadratic variation",
author = "Alexander Kel{\textquoteright}manov and Artem Pyatkin and Sergey Khamidullin and Vladimir Khandeev and Shamardin, {Yury V.} and Vladimir Shenmaier",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 7th International Conference on Optimization Problems and Their Applications, OPTA 2018 ; Conference date: 08-06-2018 Through 14-06-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-93800-4_10",
language = "English",
isbn = "9783319937991",
series = "Communications in Computer and Information Science",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "120--130",
booktitle = "Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers",
address = "Germany",

}

RIS

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