Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem
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 p...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-12-01
|
| Series: | Open Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/comp-2020-0212 |
| _version_ | 1818488005292195840 |
|---|---|
| author | Kolpakov Roman Posypkin Mikhail |
| author_facet | Kolpakov Roman Posypkin Mikhail |
| author_sort | Kolpakov Roman |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T16:45:34Z |
| format | Article |
| id | doaj.art-b97b623a0e034f41bd543ef396b8efcf |
| institution | Directory Open Access Journal |
| issn | 2299-1093 |
| language | English |
| last_indexed | 2024-12-10T16:45:34Z |
| publishDate | 2020-12-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Open Computer Science |
| spelling | doaj.art-b97b623a0e034f41bd543ef396b8efcf2022-12-22T01:41:04ZengDe GruyterOpen Computer Science2299-10932020-12-0111111612610.1515/comp-2020-0212comp-2020-0212Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum ProblemKolpakov Roman0Posypkin Mikhail1Lomonosov Moscow State University, Leninskie Gory, Moscow, RussiaandFederal Research Center “Computer Science and Control” of RAS, Vavilov st. 40, Moscow, RussiaMoscow Institute of Physics and Technology, Moscow, Russia and Federal Research Center “Computer Science and Control” of RAS, Vavilov st. 40, Moscow, RussiaIn 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.https://doi.org/10.1515/comp-2020-0212computational complexityparallel computationssubset sum problembranch-and-bound method |
| spellingShingle | Kolpakov Roman Posypkin Mikhail Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem Open Computer Science computational complexity parallel computations subset sum problem branch-and-bound method |
| title | Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem |
| title_full | Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem |
| title_fullStr | Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem |
| title_full_unstemmed | Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem |
| title_short | Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem |
| title_sort | optimality and complexity analysis of a branch and bound method in solving some instances of the subset sum problem |
| topic | computational complexity parallel computations subset sum problem branch-and-bound method |
| url | https://doi.org/10.1515/comp-2020-0212 |
| work_keys_str_mv | AT kolpakovroman optimalityandcomplexityanalysisofabranchandboundmethodinsolvingsomeinstancesofthesubsetsumproblem AT posypkinmikhail optimalityandcomplexityanalysisofabranchandboundmethodinsolvingsomeinstancesofthesubsetsumproblem |