Zobrazeno 1 - 10
of 52
pro vyhledávání: '"Roman Kolpakov"'
Autor:
Roman Kolpakov
Publikováno v:
Mathematics, Vol 10, Iss 19, p 3569 (2022)
For some fixed δ such that 0<δ<1, a δ-subrepetition in a word is a factor whose exponent is less than 2 but is not less than 1+δ (the exponent of the factor is the ratio of the factor length to its minimal period). The δ-subrepetition is maximal
Externí odkaz:
https://doaj.org/article/c1df3330e8274eaa9caf880cc07369b8
Autor:
Mikhail Posypkin, Roman Kolpakov
Publikováno v:
Open Computer Science, Vol 11, Iss 1, Pp 116-126 (2020)
In this paper we study the question of parallelization of a variant of Branch-and-Bound method for solving of the subset sum problem which is a special case of the Boolean knapsack problem. The following natural approach to the solution of this quest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::acb33e8258cb1b17f2020d573b97bb23
https://doi.org/10.1515/comp-2020-0212
https://doi.org/10.1515/comp-2020-0212
Autor:
Roman Kolpakov, Mikhail Posypkin
Publikováno v:
Discrete Mathematics and Applications. 30:313-325
An easily implementable recursive parallelization strategy for solving the subset sum problem by the branch-and-bound method is proposed. Two different frontal and balanced variants of this strategy are compared. On an example of a particular case of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e710a8ae1e0b072d2c7e326476e66cc8
https://doi.org/10.1515/dma-2020-0028
https://doi.org/10.1515/dma-2020-0028
Autor:
Mikhail Posypkin, Roman Kolpakov
Publikováno v:
Optimization Letters. 14:2211-2226
Increasing the number of computational cores is a primary way of achieving the high performance of contemporary supercomputers. However, developing parallel applications capable to harness the enormous amount of cores is a challenging task. It is ver
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9038bb8407157f1d39d558f24100c862
https://doi.org/10.1007/s11590-020-01547-6
https://doi.org/10.1007/s11590-020-01547-6
Autor:
Roman Kolpakov, Mikhail Posypkin
Publikováno v:
Diskretnaya Matematika. 31:20-37
Рассматривается легко реализуемая на практике стратегия распараллеливания при решении задачи о сумме подмножеств методом ветвей и гра
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f6131c08cb249f34deee821c8622960a
https://doi.org/10.4213/dm1526
https://doi.org/10.4213/dm1526
Autor:
Roman Kolpakov
Publikováno v:
Theoretical Computer Science. 723:11-22
For any functions $f(x)$, $g(x)$ from $\mathbb {N}$ to $\mathbb {R}$ we call repeats $uvu$ such that $g(|u|)\le |v|\le f(|u|)$ as {\it $f,g$-gapped repeats}. We study the possible number of $f,g$-gapped repeats in words of fixed length~$n$. For quite
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::82db9ff5f89e3e7a1cb999ae545b3d30
https://doi.org/10.1016/j.tcs.2018.03.007
https://doi.org/10.1016/j.tcs.2018.03.007
Autor:
Roman Kolpakov, Mikhail Posypkin
Publikováno v:
Discrete Mathematics and Applications. 28:29-34
The paper is concerned with estimating the computational complexity of the branch-and-bound method for the subset sum problem. We study the relationship between the way of decomposition of subproblems and the number of the method steps. The standard
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::362938b6f35af119bc7ca7f8008bbcee
https://doi.org/10.1515/dma-2018-0004
https://doi.org/10.1515/dma-2018-0004
Publikováno v:
Automation and Remote Control. 78:463-474
We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b082000a216fe8980ec24576ee33fa52
https://doi.org/10.1134/s0005117917030079
https://doi.org/10.1134/s0005117917030079
Autor:
Mikhail Posypkin, Roman Kolpakov
Publikováno v:
Communications in Computer and Information Science ISBN: 9783030386023
The backtracking is a basic combinatorial search algorithm. As many other deterministic methods it suffers from the high complexity. Fortunately the high performance computing can efficiently cope with this issue. It was observed that the structure o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::080bf3dffc23091ec42def26c083f84e
https://doi.org/10.1007/978-3-030-38603-0_33
https://doi.org/10.1007/978-3-030-38603-0_33
Publikováno v:
Information and Computation
Information and Computation, Elsevier, 2019, 268, pp.104434. ⟨10.1016/j.ic.2019.104434⟩
Lecture Notes in Computer Science
Information and Computation, Elsevier, 2019, 268, pp.104434. ⟨10.1016/j.ic.2019.104434⟩
Lecture Notes in Computer Science
International audience; Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34919ab4e5e2d13de1467377ce3ea684
https://hal.archives-ouvertes.fr/hal-02414845
https://hal.archives-ouvertes.fr/hal-02414845