Реферат: Abstract. In the problem considered, it is required to nd the permuta- tions tuple and the indices tuple to minimize the sum of elements chosen from a given family of nite numerical sequences subject to some con- straints on the elements choice. Namely, given a family of L numerical nonnegative N-element sequences and a positive integer J, it is required to minimize the sum of J intra-sums. In each intra-sum of L elements, each element corresponds to one element in one of L input sequences and all possible L-permutations in this one-to-one correspondence are admissible. In addition, there are some constraints on the indices of the summed sequence's elements. The problem solution is a pair of tuples, namely, (1) a tuple of the J permutations on L elements, and (2) a tuple of JL increasing indices. In the paper, we present an exact polynomial- time algorithm with O(N5) running time for this problem. The problem is induced, in particular, by an applied problem of noise-prove searching for repetitions of a given tuple of elements with their possible permuta- tions at each tuple repeat, and nding the positions of these elements in a numerical sequence distorted by noise under some constraints on unknown elements positions. The noted applied problem is related, for example, to the distant monitoring of several moving objects with pos- sible arbitrary displacements (permutations) of these objects.

Библиографическая ссылка: Mikhailova L. , Kel'manov A. , Romanchenko S.
On a problem of summing elements chosen from a family of finite numerical sequences
7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 05-07 июл. 2018