On the best choice of a branching variable in the subset sum problem

DOI10.1515/dma-2018-0004zbMath1397.90404OpenAlexW2790090683WikidataQ130192786 ScholiaQ130192786MaRDI QIDQ1744347

Roman M. Kolpakov, Mikhail A. Posypkin

Publication date: 23 April 2018

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2018-0004

zbMATH Keywords

computational complexitybranch-and-bound methodsubset sum problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Optimal strategy for solving a special case of the knapsack problem by the branch and bound method

Cites Work

• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• A criterion of optimality of some parallelization scheme for backtrack search problem in binary trees
• Graphical approach to combinatorial optimization
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
• Unnamed Item
• Unnamed Item
• Unnamed Item