𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A grid-enabled distributed branch-and-bound algorithm with application on the Steiner Problem in graphs

✍ Scribed by Lúcia M.A. Drummond; Eduardo Uchoa; Alexandre D. Gonçalves; Juliana M.N. Silva; Marcelo C.P. Santos; Maria Clícia S. de Castro

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
201 KB
Volume
32
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure of Grids in its load balance and fault tolerance procedures. This algorithm was applied over an existing code for the Steiner Problem in graphs. Experiments on real Grid conditions have demonstrated its efficiency and scalability.

📜 SIMILAR VOLUMES

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 👁 2 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

The pilot method: A strategy for heurist
The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
✍ Duin, Cees; Vo�, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 2 views

As a metaheuristic to obtain solutions of enhanced quality, we formulate the so-called pilot method. It is a tempered greedy method that is to avoid the greedy trap by looking ahead for each possible choice (memorizing the best result). Repeatedly, a so-called master solution is modified, each time

A probabilistic local majority polling g
A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
✍ Toshio Nakata; Hiroshi Imahayashi; Masafumi Yamashita 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB 👁 1 views

In this paper, we investigate a probabilistic local majority polling game on weighted directed graphs, keeping an application to the distributed agreement problem in mind. We formulate the game as a Markov chain, where an absorbing state corresponds to a system configuration that an agreement is ach