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

Alexander Kel’manov, Artem Pyatkin, Sergey Khamidullin, Vladimir Khandeev, Yury V. Shamardin, Vladimir Shenmaier

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

3 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииOptimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы120-130
Число страниц11
ISBN (печатное издание)9783319937991
DOI
СостояниеОпубликовано - 1 янв 2018
Событие7th International Conference on Optimization Problems and Their Applications, OPTA 2018 - Omsk, Российская Федерация
Продолжительность: 8 июн 201814 июн 2018

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том871
ISSN (печатное издание)1865-0929

Конференция

Конференция7th International Conference on Optimization Problems and Their Applications, OPTA 2018
СтранаРоссийская Федерация
ГородOmsk
Период08.06.201814.06.2018

Fingerprint Подробные сведения о темах исследования «An approximation polynomial algorithm for a problem of searching for the longest subsequence in a finite sequence of points in euclidean space». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    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