Back to Search
Start Over
Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem
- Source :
- Open Computer Science, Vol 11, Iss 1, Pp 116-126 (2020)
- Publication Year :
- 2020
- Publisher :
- Walter de Gruyter GmbH, 2020.
-
Abstract
- 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.
- Subjects :
- Discrete mathematics
0209 industrial biotechnology
computational complexity
General Computer Science
Computational complexity theory
Computer science
Branch and bound method
QA75.5-76.95
02 engineering and technology
subset sum problem
020901 industrial engineering & automation
parallel computations
branch-and-bound method
Electronic computers. Computer science
0202 electrical engineering, electronic engineering, information engineering
Subset sum problem
020201 artificial intelligence & image processing
Subjects
Details
- ISSN :
- 22991093
- Volume :
- 11
- Database :
- OpenAIRE
- Journal :
- Open Computer Science
- Accession number :
- edsair.doi.dedup.....acb33e8258cb1b17f2020d573b97bb23