On a problem of choosing elements in a family of sequences | Sciact - Система учета научной деятельности ИМ СО РАН

On a problem of choosing elements in a family of sequences Научная публикация

Конференция

Проблемы оптимизации и их приложения Optimization Problems and Their Applications
08-14 июл. 2018 , Омск

Журнал

CEUR Workshop Proceedings
ISSN: 1613-0073

Вых. Данные

Год: 2018, Том: 2098, Страницы: 181 - 188 Страниц : 9

Ключевые слова

Exact polynomial-time algorithm; Finite numerical sequences; Optimal summing; Permutations

Авторы

Mikhailova Ludmila ¹ , Kel'manov Alexander ^1,2 , Romanchenko Semyon ¹

Организации

1	Sobolev Institute of Mathematics
2	Novosibirsk State University

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

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

Scopus:

2-s2.0-85047997803

Пока нет цитирований