On a problem of choosing elements in a family of sequences

Alexander Kel'manov, Ludmila Mikhailova, Semyon Romanchenko

Результат исследования: Научные публикации в периодических изданияхстатья по материалам конференции

Аннотация

In the problem considered, it is required to minimize the sum of elements chosen in a family of finite numerical sequences with some constraints on the choice of elements. Namely, given a family of L nonnegative N-element sequences and a positive integer J, we need to minimize the sum of J intra-sums each of which includes only one element in every input sequence with all possible L-permutations of these sequences and under some constraints on the choice of elements to be included in the general double sum. The problem is related, for example, to the distant noise-prove monitoring of several moving objects with possible arbitrary displacements (permutations) of these objects. For this problem we present an exact polynomial-time algorithm with O(N5) running time.

Язык оригиналаанглийский
Страницы (с-по)181-188
Число страниц8
ЖурналCEUR Workshop Proceedings
Том2098
СостояниеОпубликовано - 1 янв 2018
Событие2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Российская Федерация
Продолжительность: 8 июл 201814 июл 2018

    Fingerprint

Цитировать

Kel'manov, A., Mikhailova, L., & Romanchenko, S. (2018). On a problem of choosing elements in a family of sequences. CEUR Workshop Proceedings, 2098, 181-188.