Standard
On a problem of summing elements chosen from the family of finite numerical sequences. / Kel’manov, Alexander; Mikhailova, Ludmila; Romanchenko, Semyon.
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. ed. / 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, 2018. p. 305-317 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A, Mikhailova, L & Romanchenko, S 2018,
On a problem of summing elements chosen from the family of finite numerical sequences. in A Panchenko, WM van der Aalst, M Khachay, PM Pardalos, V Batagelj, N Loukachevitch, G Glavaš, DI Ignatov, SO Kuznetsov, O Koltsova, IA Lomazova, AV Savchenko, A Napoli & M Pelillo (eds),
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11179 LNCS, Springer-Verlag GmbH and Co. KG, pp. 305-317, 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018, Moscow, Russian Federation,
05.07.2018.
https://doi.org/10.1007/978-3-030-11027-7_29APA
Kel’manov, A., Mikhailova, L., & Romanchenko, S. (2018).
On a problem of summing elements chosen from the family of finite numerical sequences. In 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 (Eds.),
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (pp. 305-317). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-030-11027-7_29Vancouver
Kel’manov A, Mikhailova L, Romanchenko S.
On a problem of summing elements chosen from the family of finite numerical sequences. In Panchenko A, van der Aalst WM, Khachay M, Pardalos PM, Batagelj V, Loukachevitch N, Glavaš G, Ignatov DI, Kuznetsov SO, Koltsova O, Lomazova IA, Savchenko AV, Napoli A, Pelillo M, editors, Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 305-317. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-11027-7_29
Author
Kel’manov, Alexander ; Mikhailova, Ludmila ; Romanchenko, Semyon. /
On a problem of summing elements chosen from the family of finite numerical sequences. Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. editor / 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, 2018. pp. 305-317 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{a7914619f1d348a9954324d9d3e55d62,
title = "On a problem of summing elements chosen from the family of finite numerical sequences",
abstract = " 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. ",
keywords = "Exact polynomial-time algorithm, Finite numerical sequences, Optimal summing, Permutations",
author = "Alexander Kel{\textquoteright}manov and Ludmila Mikhailova and Semyon Romanchenko",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-030-11027-7_29",
language = "English",
isbn = "9783030110260",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "305--317",
editor = "Alexander Panchenko and {van der Aalst}, {Wil M.} and Michael Khachay and Pardalos, {Panos M.} and Vladimir Batagelj and Natalia Loukachevitch and Goran Glava{\v s} and Ignatov, {Dmitry I.} and Kuznetsov, {Sergei O.} and Olessia Koltsova and Lomazova, {Irina A.} and Savchenko, {Andrey V.} and Amedeo Napoli and Marcello Pelillo",
booktitle = "Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers",
address = "Germany",
note = "7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 ; Conference date: 05-07-2018 Through 07-07-2018",
}
RIS
TY - GEN
T1 - On a problem of summing elements chosen from the family of finite numerical sequences
AU - Kel’manov, Alexander
AU - Mikhailova, Ludmila
AU - Romanchenko, Semyon
PY - 2018/1/1
Y1 - 2018/1/1
N2 -
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.
AB -
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.
KW - Exact polynomial-time algorithm
KW - Finite numerical sequences
KW - Optimal summing
KW - Permutations
UR - http://www.scopus.com/inward/record.url?scp=85059954814&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-11027-7_29
DO - 10.1007/978-3-030-11027-7_29
M3 - Conference contribution
AN - SCOPUS:85059954814
SN - 9783030110260
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 305
EP - 317
BT - Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
A2 - Panchenko, Alexander
A2 - van der Aalst, Wil M.
A2 - Khachay, Michael
A2 - Pardalos, Panos M.
A2 - Batagelj, Vladimir
A2 - Loukachevitch, Natalia
A2 - Glavaš, Goran
A2 - Ignatov, Dmitry I.
A2 - Kuznetsov, Sergei O.
A2 - Koltsova, Olessia
A2 - Lomazova, Irina A.
A2 - Savchenko, Andrey V.
A2 - Napoli, Amedeo
A2 - Pelillo, Marcello
PB - Springer-Verlag GmbH and Co. KG
T2 - 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
Y2 - 5 July 2018 through 7 July 2018
ER -
