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

DOI10.1134/S106423071105011XzbMATH Open1268.90131OpenAlexW2134343603MaRDI QIDQ353698FDOQ353698

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

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

Mathematics Subject Classification ID

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

Cites Work

• Optimization of schedules with precedence logical conditions
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

Cited In (4)

• 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
• An asymptotic estimate for the complexity of the branch and bound method with branching with respect to a fractional variable for the knapsack problem

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)