A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set

Thomas A. Feo,Mauricio G.C. Resende, and Stuart H. Smith

Operations Research, vol. 42, pp. 860-878, 1994


An efficient randomized heuristic for maximum independent set is presented.  The procedure is tested on randomly generated graphs having from 400 to 3500 vertices and edge probabilities from 0.2 to 0.9.  The heuristic can be trivially implemented in parallel and is tested on an MIMD computer with 1, 2, 4 and 8 processors. Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 14 March 2008

Copyright Notice