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

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

โœ Scribed by Arie Tamir

Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
688 KB
Volume
37
Category
Article
ISSN
0167-6377

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.

The critical-item, upper bounds, and a b
The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem
โœ Shaw, Dong X.; Cho, Geon ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 155 KB ๐Ÿ‘ 2 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac