Affordable Access

Access to the full text

Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method

Authors
  • Kolpakov, Roman M.1
  • Posypkin, Mikhail A.1
  • 1 Lomonosov Moscow State University, Federal Research Center “Computer Science and Control” of Russian Academy of Sciences, Russia , (Russia)
Type
Published Article
Journal
Discrete Mathematics and Applications
Publisher
De Gruyter
Publication Date
Oct 17, 2020
Volume
30
Issue
5
Pages
313–325
Identifiers
DOI: 10.1515/dma-2020-0028
Source
De Gruyter
Keywords
License
Yellow

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.

Report this publication

Statistics

Seen <100 times