On a problem of summing elements chosen from the family of finite numerical sequences

Alexander Kel’manov, Ludmila Mikhailova, Semyon Romanchenko

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

Аннотация

The tuple of permutations and the tuple of indices are required to be found in the problem considered in order to minimize the sum of elements chosen from the given family of finite numerical sequences subject to some constraints on the elements choice. Namely, given the family of L numerical nonnegative N-element sequences and a positive integer J, it is required to minimize the sum of J intra-sums. Each element corresponds to one element in one of L input sequences, and all possible L-permutations are admissible in this one-to-one correspondence in each intra-sum of L elements. In addition, there are some constraints on the indices of the summed sequence elements. The problem solution is a pair of tuples, namely, (1) a tuple of J permutations on L elements, and (2) a tuple of JL increasing indices. The paper presents an exact polynomial-time algorithm with O(N 5 ) running time for this problem. In particular, the problem is induced by an applied problem of noiseproof searching for repetitions of the given tuple of elements with their possible permutations at each tuple repeat, and finding the positions of these elements in the numerical sequence distorted by noise under some constraints on unknown positions of elements. The applied problem noted is related, for example, to the remote monitoring of several moving objects with possible arbitrary displacements (permutations) of these objects.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
РедакторыAlexander Panchenko, Wil M. van der Aalst, Michael Khachay, Panos M. Pardalos, Vladimir Batagelj, Natalia Loukachevitch, Goran Glavaš, Dmitry I. Ignatov, Sergei O. Kuznetsov, Olessia Koltsova, Irina A. Lomazova, Andrey V. Savchenko, Amedeo Napoli, Marcello Pelillo
ИздательSpringer-Verlag GmbH and Co. KG
Страницы305-317
Число страниц13
ISBN (печатное издание)9783030110260
DOI
СостояниеОпубликовано - 1 янв 2018
Событие7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 - Moscow, Российская Федерация
Продолжительность: 5 июл 20187 июл 2018

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

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11179 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
СтранаРоссийская Федерация
ГородMoscow
Период05.07.201807.07.2018

Fingerprint Подробные сведения о темах исследования «On a problem of summing elements chosen from the family of finite numerical sequences». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kel’manov, A., Mikhailova, L., & Romanchenko, S. (2018). On a problem of summing elements chosen from the family of finite numerical sequences. В A. Panchenko, W. M. van der Aalst, M. Khachay, P. M. Pardalos, V. Batagelj, N. Loukachevitch, G. Glavaš, D. I. Ignatov, S. O. Kuznetsov, O. Koltsova, I. A. Lomazova, A. V. Savchenko, A. Napoli, & M. Pelillo (Ред.), Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (стр. 305-317). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11179 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-11027-7_29