๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by R. M. Kolpakov; M. A. Posypkin

Book ID
111454023
Publisher
SP MAIK Nauka/Interperiodica
Year
2011
Tongue
English
Weight
456 KB
Volume
50
Category
Article
ISSN
1064-2307

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Bounds on the size of branch-and-bound p
Bounds on the size of branch-and-bound proofs for integer knapsacks
โœ Bala Krishnamoorthy ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 172 KB

Using a direct counting argument, we derive lower and upper bounds for the number of nodes enumerated by linear programming-based branch-and-bound (B&B) method to prove the integer infeasibility of a knapsack. We prove by example that the size of the B&B tree could be exponential in the worst case.