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

DOI10.1515/DMA-2018-0004MaRDI QIDQ1744347zbMATH OpenOpenAlexWikidataFDO

Authors Roman Kolpakov, M. 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

branch-and-bound methodcomputational complexitysubset 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)

Recommendations

• Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• The subset sum problem
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

Cites work

• A criterion of optimality of some parallelization scheme for backtrack search problem in binary trees
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• An asymptotic estimate for the complexity of the branch and bound method with branching with respect to a fractional variable for the knapsack problem
• Graphical approach to combinatorial optimization
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

Cited in

(5)

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering
• Optimal strategy for solving a special case of the knapsack problem by the branch and bound method
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method

This page was built for publication: On the best choice of a branching variable in the subset sum problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1744347)