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

Branch and bound methods for a search problem

โœ Scribed by Alan R. Washburn

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
116 KB
Volume
45
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The problem of searching for randomly moving targets such as children and submarines is known to be fundamentally difficult, but finding efficient methods for generating optimal or near optimal solutions is nonetheless an important practical problem. This paper investigates the efficiency of Branch and Bound methods, with emphasis on the tradeoff between the accuracy of the bound employed and the time required to compute it. A variety of bounds are investigated, some of which are new. In most cases the best bounds turn out to be imprecise, but very easy to compute.

๐Ÿ“œ 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

Approximation bounds for Black Hole Sear
Approximation bounds for Black Hole Search problems
โœ Ralf Klasing; Euripides Markou; Tomasz Radzik; Fabiano Sarracco ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 329 KB

## Abstract A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of

Enhancing CLP branch and bound technique
Enhancing CLP branch and bound techniques for scheduling problems
โœ F. Bosi; M. Milano ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 280 KB

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing