Roman Kolpakov

The paper about the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics of Lomonosov Moscow State University discusses the issues of

Summary: In the paper, we compute some lower bounds on time of parallel solving of the subset sum problem on a big number of processors by several versions of dynamic programming algorithm Balsub proposed before by Pisinger. Based on these lower bounds, we propose a version of Balsub which could be possibly effectively parallelized.

In this paper, we consider a tree-like recursion procedure of solving of binary decomposable problems. More specifically, we study some questions of parallelization of this procedure with using of shared round memory. We consider two parallelization schemes for parallel solving of binary decomposable problems by tree-like recursion procedures on a parallel computing system with shared round memory. We call these schemes the TAN-scheme and the TON-scheme of parallelization. We compare the efficiency of these schemes, using different parameters of parallelization. Based on this comparative analysis, we conclude the TON-scheme to be more effective.

The exponent of a formal word is the relation between its length and its minimal period. A repetition (subrepetition) in a word is a factor of exponent not less than 2 (less than 2). A gapped repeat in a word is a pair of identical factors with a positive gap between these factors. In the paper we present a review of some new results concerning the possible number of repetitions, subrepetitions and gapped repeats in words of fixed length .

A particular case of the knapsack problem is considered for which the weights of all items are identical and the costs of the items take just two different

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 question is considered. At the first stage one of the processors (control processor) performs some number of algorithm steps of solving a given problem with generating some number of subproblems of the problem. In the second stage the generated subproblems are sent to other processors for solving (one subproblem per processor). Processors solve completely the received subproblems and return their solutions to the control processor which chooses the optimal solution of the initial problem from these solutions. For this approach we define formally a model of parallel computing (frontal parallelization scheme) and the notion of complexity of the frontal scheme. We study the asymptotic behavior of the complexity of the frontal scheme for two special cases of the subset sum problem.