Greedy randomized adaptive search procedures for the Steiner problem in graphs

S.L. Martins, P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro

In Randomization methods in algorithm design, P.M. Pardalos, S. Rajasekaran, and J. Rolim, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 43, pp. 133-145, 1999


We describe four versions of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions of general
instances of the Steiner Problem in Graphs.  Different construction and local search algorithms are presented.  Preliminary computational results with one of the versions on a variety of test problems are reported.  On the majority of instances from the OR-Library, a set of standard test problems, the GRASP produced optimal solutions.  On those that optimal solutions were not found, the GRASP found good quality approximate solutions.

PostScript file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice