Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
Authors:
- 1 October 2020
- journal article
- research article
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 30 (5) , 313-325
Abstract
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 the subset sum problem we show that the balanced variant is more effective than the frontal one. Moreover, we show that, for the considered particular case of the subset sum problem, the balanced variant is also time optimal.Keywords
Funding Information
- Russian Science Foundation (18-07-00566 A)
This publication has 7 references indexed in Scilit:
- On the best choice of a branching variable in the subset sum problemDiscrete Mathematics and Applications, 2018
- Space-efficient parallel algorithms for combinatorial search problemsJournal of Parallel and Distributed Computing, 2015
- Upper and lower bounds for the complexity of the branch and bound method for the knapsack problemDiscrete Mathematics and Applications, 2010
- Knapsack Problems2004
- Deterministic parallel backtrack searchTheoretical Computer Science, 2002
- Tight Bounds for On-Line Tree EmbeddingsSIAM Journal on Computing, 1999
- Randomized parallel algorithms for backtrack search and branch-and-bound computationJournal of the ACM, 1993