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
ABSTRACT
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 PageLast modified: 28 June 2002