𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem

✍ Scribed by Shaw, Dong X.; Cho, Geon

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
155 KB
Volume
31
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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 packed. In this paper, we first define the so-called critical-item for the TKP and present an algorithm to find it. Then, we develop several upper bounds for the TKP. Finally, we present a branch-and-bound procedure for solving the TKP. Our computational results might suggest that our code is currently the most efficient procedure available in the literature.

πŸ“œ SIMILAR VOLUMES

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 256 KB πŸ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 165 KB πŸ‘ 1 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

A branch-and-cut algorithm for the undir
A branch-and-cut algorithm for the undirected selective traveling salesman problem
✍ Gendreau, Michel; Laporte, Gilbert; Semet, FrοΏ½dοΏ½ric πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 120 KB πŸ‘ 1 views

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a p

A fast algorithm for a k-NN classifier b
A fast algorithm for a k-NN classifier based on the branch and bound method and computational quantity estimation
✍ Shin'ichiro Omachi; Hirotomo Aso πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 173 KB πŸ‘ 2 views

The nearest neighbor rule or k-nearest neighbor rule is a technique of nonparametric pattern recognition. Its algorithm is simple and the error is smaller than twice the Bayes error if there are enough training samples. However, it requires an enormous amount of computation, proportional to the numb

A branch-and-cut algorithm for the resou
A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
✍ Fischetti, Matteo; Vigo, Daniele πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 1 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.