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
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
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002