Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering

DOI10.1134/S0005117917030079zbMath1369.90196OpenAlexW2593592449MaRDI QIDQ2399471

Si Tu Tant Sin, Roman M. Kolpakov, Mikhail A. Posypkin

Publication date: 23 August 2017

Published in: Automation and Remote Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0005117917030079

zbMATH Keywords

computational complexityknapsack problembranch-and-bound methoddomination relation

Mathematics Subject Classification ID

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

Related Items (1)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems

Cites Work

• Unnamed Item
• Unnamed Item
• An exact algorithm for large unbounded knapsack problems
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• Graphical approach to combinatorial optimization
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

This page was built for publication: Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering