Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem

DOI10.1134/S106423071105011XMaRDI QIDQ353698zbMATH OpenOpenAlexFDO

Authors Roman Kolpakov, M. A. Posypkin

Publication date 16 July 2013

Published in Journal of Computer and Systems Sciences International (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method
• Approximate algorithms for the Knapsack problem on parallel computers
• Investigation of algorithms of parallel computations in knapsack-type discrete optimization problems
• Efficiency considerations in the implementation of parallel branch-and- bound
• Performance of parallel branch-and-bound algorithms
• scientific article; zbMATH DE number 2075843
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
• Parallel approximation schemes for subset sum and knapsack problems
• The Computational Complexity of the Parallel Knock-Out Problem

Cites work

• scientific article; zbMATH DE number 5849341 (Why is no real title available?)
• scientific article; zbMATH DE number 5654190 (Why is no real title available?)
• An asymptotic estimate for the complexity of the branch and bound method with branching with respect to a fractional variable for the knapsack problem
• Exact and greedy solutions of the knapsack problem: the ratio of values of objective functions
• Optimization of schedules with precedence logical conditions

Cited in

(4)

• An asymptotic estimate for the complexity of the branch and bound method with branching with respect to a fractional variable for the knapsack problem
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
• On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method
• The scalability analysis of a parallel tree search algorithm

This page was built for publication: Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem

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