@incollection{AbeParRes99a,
	author = "J. Abello and P.M. Pardalos and M.G.C. Resende",
	title = "On maximum clique problems in very large graphs",
	booktitle = "External memory algorithms and visualization",
	editor = "J. Abello and J. Vitter",
        series = "{DIMACS} Series on Discrete Mathematics and Theoretical
                  Computer Science",
	publisher = "American Mathematical Society",
	volume = "50",
	pages = "119--130",
	year = "1999",
        annote   =	"An approach for clique and quasi-clique
                	computations in very large multi-digraphs is presented.
                	The authors discuss graph decomposition schemes
                	that break up the original problem into several
                	pieces of manageable dimensions. A semi-external
                	memory {GRASP}
                	is presented to approximately solve the maximum clique
                	problem and maximum quasi-clique problem.
                	The construction phase uses vertex degrees
                	as a guide for construction. The local search uses a
                	simple $(2,1)$-exchange."
}

@Article{AbeResSud02a,
        author = {J. Abello and M.G.C. Resende and S. Sudarsky},
        title = {Massive quasi-clique detection},
        journal = {Lecture Notes in Computer Science},
	volume = {2286},
	pages = {598--612},
	annote = {Detecting dense subgraphs (quasi-cliques) in massive 
		sparse graphs whose vertex set fits in RAM is a hard 
		problem. 
		In this paper, a {GRASP} is designed for extracting 
		dense subgraphs on case of both nonbipartite and 
		bipartite case. 
		In case of nonbipartite graphs, the construction 
		procedure applies a greedy criterion based on 
		a measure of the effect of elements selection on 
		the potential of the other vertices. 
		In the bipartite case, the authors adapt the above 
		greedy criterion to a slight different definition 
		of potential. 
		In both cases, the neighborhood structure used 
		is a $(2,1)$-exchange.},
	year = {2002}
}

@Article{AhuOrlSha01a,
	author = "R.K. Ahuja and J.B. Orlin and D. Sharma",
	title = "Multi-exchange neighborhood search structures for the
                 capacitated minimum spanning tree problem",
	journal = "Mathematical Programming",
	volume = "91",
	pages = "71-97",
	year = "2001",
        annote   =     "The main contribute of this paper is the proposal of 
			two very large scale neighborhood search algorithms. 
			The first one uses a node based neighborhood structure, 			defined by performing multi-exchanges involving several 
			trees, where each tree contributes a subtree. 
			The second algorithm uses instead a tree based 
			neighborhood structure, obtained by allowing 
			multi-exchanges, where each tree contributes a 
			subtree. 
			The authors compare their algorithms with the best 
			state-of-the-art approaches, including a {GRASP}.",
}

@Article{AhuOrlSha03a,
        author = {R.K. Ahuja and J.B. Orlin and D. Sharma},
        title = {A composite very large-scale neighborhood structure for 
	         the capacitated minimum spanning tree problem},
        journal = {Operations Research Letters},
        volume = {31},
	number = {3},
	pages = {185--194},
	annote = {The authors propose a composite neighborhood structure 
		that combines both the node based and the tree based 
		neighborhoods already proposed in Ahuja et al. (2001). 
		They compare their algorithm with the best state-of-art 
		methods, including a {GRASP}.},
	year = {2003}
}

@techreport{AlvGonDeA03a,
        author = {A.M. \'Alvarez and J. L. Gonz\'alez and K. De-Alba},
        title = {Scatter search for a network design problem},
	number = {PISIS-2003-02},
	institution = {Universidad Aut\'onoma de Nuevo Le\'on,
		       Facultad de Ingenier\'{\i}a Mec\'anica y El\'ectrica,
	               Divisi\'on de Posgrado en Ingenier\'{\i}a 
		       de Sistemas, Mexico.},
	annote = {The authors propose a Scatter Search (SS) algorithm 
		for solving a fixed charge capacitated multicommodity 
		network design problems on undirected networks. 
		SS is an evolutionary method that constructs new solutions 
		by combining others. 
		It performs the following three basic steps: 1) generation of 
		a population $P$; 2) extraction of a reference set $R$; 
		3) combination of elements from $R$ and updating of $R$. 
		The different ways SS can be implemented consists in designing 
		several different subroutines, including a Diversification 
		Generation Method (DGM). 
		The DGM proposed in this paper is a {GRASP} with some 
		memory features incorpored. 
		More in detail, in the {GRASP} DGM for each commodity 
		a certain number $q$ of shortest paths between each 
		origin-destination pair are kept as RCL elements. 
		The local search consists basically in sorting the chosen 
		paths and possibly exchange some of them in order to get 
		a better distribution.},
	year = {2003}
}

@inproceedings{ArrMarMezOrt01a,
        author = "E. Arr\'aiz and A. Mart\'{\i}nez and O. Meza and M. Ortega",
        title = "{GRASP} and tabu search algorithms for computing the 
		forwarding index in a graph",
        booktitle = "Proceedings of MIC'2001",
        city = "Porto, Portugal",
        month = "July 16-20",
        year = "2001",
        pages = "367--370",
	annote = "The forwarding index in a graph is a measure of the load or 
		of the congestion of vertices once the paths between vertices 
		have been computed. 
		For efficiently computing this number, the authors propose 
		a {GRASP} and tabu search algorithms. 
		The {GRASP} greedy choice considers the length of paths connecting 
		nonadjacent nodes, while two different local search strategies are used. 
		The first one replaces a path passing through an internal node with 
		maximum load with another path joining the same endpoints. 
		The second one replaces a path with maximum length."
}

@techreport{BoeRibBlo03a,
        author = {M.C. Boeres and C.C. Ribeiro and I. Bloch},
        title = {{Randomized algorithms for scene recognition by inexact 
		graph matching}},
        institution = {Computer Science Department, Catholic University of
	               Rio de Janeiro},
	address = {Rio de Janeiro, Brazil},
        annote = {This paper proposes a new algorithm to suboptimally solve 
		non-bijective graph matching for model-based pattern 
		recognition. 
                The algorithm consists of a randomized construction 
		procedure and a local search procedure. 
		In the construction procedure, the used greedy function has 
		two terms representing respectively the node and edge 
		contributions to the measure of the solution quality 
		associated with the corrispondence. 
		Given a feasible solution $x$, the neighborhood structure 
		used during local search considers as neighbors of $x$ 
		all feasible solutions that can be obtained by changing 
		some association.},
        year = {2003}
}

@Article{CanResRib01a,
        author = "S.A. Canuto and M.G.C. Resende and C.C. Ribeiro",
        title = "Local search with perturbation for the prize-collecting
                 {Steiner} tree problems in graphs",
        journal = "Networks",
        volume = "38",
        pages = "50--58",
        year = "2001",
        annote   = "Several local search strategies have been investiged 
		in this paper for solving the prize-collecting {Steiner} 
		tree problems in graphs, including path relinking, VNS, 
		and a {GRASP} that uses some cost perturbations. 
		The greedy choice takes into account the input edge weights, 
		while the local search routine defines as neighborhood 
		of a solution $T(X)$ the set of all minimum spanning 
		trees $T(X')$, where $X'$ differs from $X$ for exactly 
		one node.",
}

@techreport{FioMal03b,
        author = "M.S. Fiorenzo Catalano and F. Malucelli",
        title = "Parallel randomized heuristics for the set covering problem",
        note = "To appear in International J. of Computer Research",
	institution = {Transportation and traffic engineering section,
	               Delft U. of Technology, 2600 AG Delft, The Netherlands},
        year = "2000",
        annote   =     "The authors propose a general scheme to design heuristics 
			for the set covering problem. 
			A first group of procedures randomize the choice of the next 
			element to be added at the solution under construction in 
			a way similar to ant system, while a second set of 
			procedures introduces a random perturbation of the costs 
			of the problem instance. 
			The second set includes also a {GRASP} and seems to be more 
			efficient than competitors from the first set of algorithms.",
}

@Article{CorMarSan02a,
	 author = "A. Corber\'an and R. Mart\'{\i} and J.M. Sanch\'{\i}s",
	 title = "A {GRASP} heuristic for the mixed {C}hinese postman problem",
	journal = "European Journal of Operational Research",
	volume = "142",
	pages = "70--80",
	year = "2002",
        annote   =     "Given a strongly connected mixed graph $G(V,E,A,c)$, 
			where $V$ is the node set, $E$ is the set of 
			undirected edges, $A$ is the set of directed arcs, 
			and $c$ is a nonnegative cost function defined in 
			$E\cup A$, then the mixed {C}hinese postman problem 
			consists in finding a minimum cost tour passing 
			through each link $e\in E\cup A$ at least once. 
			The construction phase of the proposed {GRASP} 
			uses a greedy function based on the definition of the 
			degree of a node in terms of both incident oriented 
			arcs and incident undirected edges. 
			Each iteration of the local search procedure selects 
			a pair of vertices $u,v\in V$ that are candidates for 
			the move if they are joined by a path of duplications.",
}

@Incollection{SouDuhRib03a,
          author = "M.C. de Souza and C. Duhamel and C.C. Ribeiro",
         title = "A {GRASP} heuristic for the capacitated minimum spanning 
		  tree problem using a memory-based local search strategy",
	 booktitle = "Metaheuristics: Computer decision-making", 
         editor = "M.G.C. Resende and J.P. de Sousa",
	 publisher = {Kluwer Academic Publishers},
         pages = "627--658",
         year = "2003",
        annote   =     "In this paper, the authors propose a novel local 
			search that applies reduction techniques to speed 
			up the search and uses a new path-based neighborhood 
			structure, defined by path exchanges. 
			Each edge $e$ having extremities into two different 
			components of $T$ is considered a candidate for 
			being inserted into the current tree, but immediately 
			discarded (reduction strategy) if it does not respect 
			some conditions that depend on three criteria and 
			that, if verified, ensure that it is unlikely that 
			the involved edge can be part of an improving 
			move. 
			One criterion is based on the relative cost $r(e)$ 
			of the edge $e$, i.e. the difference between the 
			weight of a minimum spanning tree and the weight of 
			a constrained spanning tree in which the presence 
			of $e$ is enforced. 
			Another criterion is based on the decomposition 
			of the cost of a move defined by the candidate edge 
			$e$ for insertion and by a candidate path $(p--q)$ 
			(from $p$ to $q$) for removal. 
			The cost $\Delta$ of such a move can be written as 
			$\Delta=\Delta_1+\Delta_2$, where $\Delta_1$ is 
			associated with the edge exchanges that will generate 
			the component containing $e$ in the new solution, 
			while $\Delta_2$ is given by the reconnection of 
			the remaining elements along the candidate path 
			$(p--q)$. 
			The third criterion does not compute $\Delta_2$ 
			and uses a lower bound $\delta\leq \delta_1$: 
			a candidate edge $e$ is discarded if $\delta\geq 0$ 
			for each possible candidate path $(p--q)$ that 
			can be used in conjunction with $e$.
			The authors also propose a {GRASP} that uses the same 
			neighborhood structure as the previously described 
			local search and some short term memory elements 
			of tabu search and that implements a randomized 
			version of a savings heuristic in the construction 
			phase. 
			A post-optimization phase is realized by applying 
			a path-relinking procedure.",
}

@Article{FeoRes89a,
	author = "T.A. Feo and M.G.C. Resende",
	title = "A probabilistic heuristic for a computationally
		 difficult set covering problem",
	journal = "Operations Research Letters",
	volume = "8",
	pages = "67--71",
	year = "1989",
        annote   =     "{GRASP} is proposed for set covering.
                	A value based restricted candidate list is used 
			to construct solutions of difficult set covering 
			problems that arise in computing
                	the $1$-width of the incidence matrix of Steiner triple
                	systems. 
			The local search is based on the elimination
                	of redundant elements in the cover.",
}

@Article{FeoResSmi94a,
	author = "T.A. Feo and M.G.C. Resende and S.H. Smith",
	title = "A greedy randomized adaptive search procedure for
                 maximum independent set",
	journal = "Operations Research",
	volume = "42",
	pages = "860--878",
	year = "1994",
        annote   =     "A {GRASP} for approximately solving the
                	maximum independent set problem is described.
                	The greedy function chosen orders admissible vertices
                	with respect to the minimum admissible vertex degree.
                	The adjective admissible is referred to a vertex that
                	is not adjacent to any vertex in the current independent
                	set. 
			The neighborhood definition used in the local search
                	is $(2,1)$-exchange, where two nonadjacent vertices
                	can be added to the current solution if a single vertex
                	from the solution is removed.
                	The proposed heuristic can be easily implemented in
                	parallel by decomposing the problem into smaller
                	subproblems, each defined by conditioning on vertices
                	being in the solution.
                	An implementation of this algorithm was tested
                	on a MIMD computer with up to eight processors.
                	Average linear speedup is observed.",
}

@Article{FesParResRib02a,
        author = "P. Festa and P.M. Pardalos and M.G.C. Resende and 
		  C.C. Ribeiro",
        title = "Randomized heuristics for the {MAX-CUT} problem",
        journal = "Optimization Methods and Software",
	volume = "7",
	pages = {1033--1058},
        year = "2002",
        annote   =     {Given an undirected graph with edge weights,
			the  max-cut problem consists in finding a partition of
			the nodes into two subsets, such that the sum of the 
			weights of the edges having endpoints
			in different subsets is maximized.
			For solving this well-known NP-hard problem, 
			the authors propose and test a {GRASP}, a variable 
			neighborhood search (VNS), a path relinking 
			intensification heuristic, and new hybrid heuristics 
			that combine {GRASP}, VNS, and path relinking. 
			The greedy function of the pure {GRASP} is related 
			to the sum of the weights of the edges in each cut. 
			Let $(S,\bar S)$ be the current cut solution and let 
			$v\in V$ be a vertex, then the pure {GRASP} local 
			search associates to $v$ either the neighbor
			$(S \setminus \{v\}, \bar S\cup \{v\})$ if $v \in S$,
			or the neighbor 
			$(S \cup \{v\}, \bar S \setminus \{v\})$ otherwise.
			Computational results indicate that the proposed 
			randomized heuristics find near-optimal solutions.
			On a set of standard test problems, new best known 
			solutions were produced for many of the instances.},
}

@Article{HamRad01a,
        author = "P.L. Hammer and D.J. {Rader,~Jr.}",
        title = "Maximally disjoint solutions of the set
                 covering problem",
        journal = "Journal of Heuristics",
        volume = "7",
        pages = "131--144",
        year = "2001",
        annote   =     "This paper describes the problem of finding
                	two solutions of a set covering problem that have a minimum
                	number of common variables. It is proved that this problem is
                	NP-complete and three heuristics are proposed
                	for solving it.
                	Two of these algorithms find the solutions sequentially.
                	One of them is a {GRASP}. The third algorithm finds
                	solutions simultaneously. Each proposed heuristic is a variant
                	of the standard greedy method for set covering problems, whose
                	greedy choice favors unselected variables that maximize
                	the number of uncovered rows that become covered. To reduce
                	the overlap of any pair of solutions, a local search algorithm
                	is used that swaps at each iteration parts of the
                	solution found with a set of variables not in it.",
}

@incollection{HolMigPar98a,
	author = "K. Holmqvist and A. Migdalas and P.M. Pardalos",
	title = "A {GRASP} algorithm for the single source uncapacitated
                 minimum concave-cost network flow problem",
	booktitle = "Network design: {C}onnectivity and facilities
                     location",
	editor = "P.M. Pardalos and D.-Z. Du",
        series = "{DIMACS} Series on Discrete Mathematics and Theoretical
                  Computer Science",
	publisher = "American Mathematical Society",
        volume = "40",
	pages = "131--142",
	year = "1998",
        annote =     	"This paper is concerned with the single source
                	uncapacitated version of the minimum concave-cost 
			network flow problem, that requires establishing a 
			minimum cost flow through a given network from a 
			single source to a set of sinks. 
			The authors propose a {GRASP} that
                	can be trivially implemented on parallel processors.
                	The construction phase iteratively builds a tree 
			starting from the source node. The elements of the 
			restricted candidate list are end nodes of arcs with 
			a cost close to the best one. The local search phase 
			applies either of the two local search variants 
			proposed by Guisewite and Pardalos (1990)."
}

@inproceedings{KumSriWanLanRam01a,
     	author = {K. Kumaran and A. Srinivasan and Q. Wang and S. Lanning 
               and K.G. Ramakrishnan},
     	title = {Efficient algorithms for location and sizing problems in 
              network design},
     	booktitle = {Global Telecommunications Conference, 2001 (GLOBECOM '01)},
     	publisher = {IEEE},
     	volume = {4},
	annote = {The authors develop algorithms based on linear programming 
		and a slight modified {GRASP}, in which the costruction phase 
		is performed at random. 
		Given an initial solution, the local search procedure 
		exhaustively evaluate objective function value for all 
		possible single location changes.},
     	year = {2001},
     	pages = {2586--2590}
}

@Article{LagMar01b,
	author = "M. Laguna and R. Mart\'{\i}",
	title = "A {GRASP} for coloring sparse graphs",
	journal = "Computational Optimization and Applications",
	volume = "19",
	pages = "165--178",
	year = "2001",
        annote   =     "A {GRASP} for graph coloring is presented.
                	The {GRASP} construction phase constructs the next coloring, one
                	color at time. The greedy function chooses the vertex having
                	the maximum degree among the uncolored vertices adjacent to
                	at least one colored vertex. At each step, the local search
                	combines the two smallest cardinality color classes into one
                	and tries to find a valid color for each violating vertex.",
}

@techreport{MacSou97b,
	author = "E.M. Macambira and C.C. de Souza",
        title = "The edge-weighted clique problem: {V}alid inequalities, 
		facets and polyhedral computations",
        number = "IC-97-14",
        institution = "Instituto de Computa\c c\~ao,
                       Universidade Estadual de Campinas",
        address = "Campinas, Brazil",
	annote = "Given a complete undirected graph $K_n=(V,E)$ with weights 
		$c_e$ associated to edges in $E$, the edge-weighted clique 
		problem consists in finding a subclique $C=(U,F)$ of $K_n$ 
		such that the sum of the weights of the edges in $F$ is 
		maximized and $\vert U\vert\leq b$, for some 
		$b\in \{1,2,\ldots,n\}$. 
		In this paper, the facial structure of the polytope 
		associated to the problem is studied and new classes of 
		facies are introduced. 
		To obtain initial lower bounds, the authors used a {GRASP}.",
        year = "1997"
}

@inproceedings{MacSou97a,
	author = "E.M. Macambira and C.C. de Souza",
	title = "A {GRASP} for the maximum clique problem with
                 weighted edges",
	booktitle = "Proceedings of the XXIX Brazilian Symposium on
                    Operations Research",
        month = "October",
	year = "1997",
	pages = "70",
	annote =	"The authors propose a branch-and-cut
                	algorithm for the maximum clique problem with weighted
                	edges. The initialization phase of the algorithm uses a
                	{GRASP} to generate good starting solutions. The
                	greedy function minimizes the sum of weights of the
                	edges outgoing from vertices in the partition. The
                	local search uses the exchange of one element in the
                	current partition with one not in it."
}

@techreport{MacMen98a,
	author = "E.M. Macambira and C.N. Meneses",
	title = "A {GRASP} algorithm for the maximum weighted edge
                 subgraph problem",
	institution = "Department of Statistics and Computation,
                       University of Cear\'a",
	address = "Fortaleza, CE 60740-000 Brazil",
	year = "1998",
	annote = 	" {GRASP} for the maximum weighted edge subgraph
                	problem is proposed to overcome the difficulties
                	encountered by local search methods. 
			The greedy function of the construction phase favors 
			the vertices corresponding to the maximum sum of the 
			weights associated with its outgoing edges. 
			The local search tries to improve the
                	actual solution by simply swapping one element in the
                	solution set with one not belonging to the solution.
                	In Portuguese."
}

@techreport{MarMig03a,
        author = "Y. Marinakis and A. Migdalas",
        title = "Expading neighborhood {GRASP} for the {T}raveling 
		{S}alesman {P}roblem",
        institution = "Technical University of Crete",
        address = "Chania 73100, Greece",
	annote = {For the traveling salesman problem the authors 
		of this paper propose a {GRASP} that includes 
		tour improvement methods. 
		One among the simplest tour improvement method is 
		the nearest neighbor in which at each step the salesman 
		moves to the city nearest to the current one.},
        year = "2003"
}

@Article{Mar01a,
	author = "R. Mart\'{\i}",
	title = "Arc crossing minimization in graphs with {GRASP}",
	journal = "IIE Transactions",
	volume = "33",
	pages = "913--919",
	year = "2001",
        annote   =     "A {GRASP} for minimizing straight-line crossings
                   	in hierarchical graphs is presented.
                   	{GRASP} is shown to be faster than more complex
                   	heuristics but produces lower-quality solutions.
                   	It is not as fast as simple heuristics, but
                   	finds better-quality solutions.
                   	Hence, it is a candidate for practical implementation
                   	in graph drawing systems.",
}

@Article{MarEst01a,
	author = "R. Mart\'{\i} and V. Estruch",
	title = "Incremental bipartite drawing problem",
	journal = "Computers and Operations Research",
	volume = "28",
	pages = "1287--1298",
	year = "2001",
        annote   =     "The goal of limiting the number of arc crossings is a
                	well accepted criterion of how well a graph is drawn.
                	Incremental graph drawing supports interactive updates
                	by users.
                	A {GRASP} is proposed for the incremental arc crossing
                	minimization problem for bipartite graphs.
                	Computational experiments are done on 450 instances and
                	results are compared with a branch and bound algorithm.",
}

@article{MarLag03a,
	author = "R. Mart\'{\i} and M. Laguna",
	title = "Heuristics and meta-heuristics for $2$-layer straight
                 line crossing minimization",
	journal = {Discrete Applied Mathematics},
	volume = {127},
	pages = {665-678},
	year = "2003",
	annote = 	"Extensive computational results are presented using 12
              		heuristics and two meta-heuristics for the $2$-layer 
			straight line crossing minimization problem. 
			On dense graphs, a tabu search meta-heuristic does 
			best with {GRASP} a close second. 
			On low-density graphs, {GRASP} outperforms all
              		other approaches."
}

@incollection{MarParResRib99a,
	author = "S.L. Martins and P.M. Pardalos and M.G.C. Resende and
                  C.C. Ribeiro",
	title = "Greedy randomized adaptive search procedures for
		 the {Steiner} problem in graphs",
	booktitle = "Randomization methods in algorithmic design",
	editor = "P.M. Pardalos and S. Rajasekaran and J. Rolim",
        series = "{DIMACS} Series on Discrete Mathematics and Theoretical
                  Computer Science",
	publisher = "American Mathematical Society",
        volume = "43",
        pages = "133--145",
	year = "1999",
        annote =	"Four versions of a {GRASP} for approximately
                	solving general instances of the Steiner problem in 
			graphs are proposed.
                	One is implemented and tested.
                	The construction phase is based on the distance 
			network heuristic. A distance
                	network corresponding to the original graph is built.
                	Associated with each edge of the distance network is a 
			weight that takes into account the shortest distances 
			in the original graph. 
			With respect to the new weight distribution,
                	Kruskal's algorithm is used to solve the minimum 
			spanning tree (MST) problem and the edges in the MST 
			so computed are replaced by the edges in the 
			corresponding shortest paths in the original graph. 
			The local search is based on insertions and 
			eliminations of nodes to and from the current
                	solution."
}

@Article{MarResRibPar00b,
	author = "S.L. Martins and M.G.C. Resende and C.C. Ribeiro and
			  P.M. Pardalos",
        title = "A parallel {GRASP} for the {Steiner} tree problem in graphs
                  using a hybrid local search strategy",
        journal = "Journal of Global Optimization",
        volume = "17",
        year = "2000",
        pages = "267--283",
        annote   =     "This paper presents a {GRASP} for the Steiner
                	problem in graphs.  The construction phase is
                	based on the Mehlhorn distance network heuristic, which
                	consists of computing the modified distance network graph
                	and using Kruskal's algorithm to solve the minimum spanning
                	tree problem for the resulting graph. The local search is
                	done by using a combination of key-path based local search
                	and node based local search.",
}

@incollection{MarRibSou98a,
	author = "S.L. Martins and C.C. Ribeiro and M.C. Souza",
	title = "A parallel {GRASP} for the {S}teiner problem in
		 graphs",
	booktitle = "Proceedings of {IRREGULAR}'98 -- 5th {I}nternational
		     {S}ymposium on {S}olving {I}rregularly {S}tructured
		     {P}roblems in {P}arallel",
	editor = "A. Ferreira and J. Rolim",
        series = "Lecture Notes in Computer Science",
	publisher = "Springer-Verlag",
        volume = "1457",
        pages = "285--297",
	year = "1998",
        annote   =     	"A parallelization of a sequential {GRASP}
                	for the Steiner minimal tree problem is proposed. The
                	procedure implemented is one of the procedures described
                	in Martins, Pardalos, Resende, and Ribeiro (1999).
                	The parallelization is accomplished by distributing the
                	{GRASP} iterations among the processors on a 
			demand-driven basis."
}

@inproceedings{MotOchMar01a,
        author = "L. Motta and L.S. Ochi and C. Martinhon",
        title = {{GRASP} metaheuristics to the generalized covering 
	          tour problem},
        booktitle = "Proceedings of MIC'2001",
        city = "Porto, Portugal",
        month = "July 16-20",
        pages = "387--391",
        annote = {Let $G(V\cup W,E)$ be an undirected graph, where
                $V\cup W=\{1,2,\ldots,n\}$ is the node set, and
                $E=\{(i,j)\vert i,j\in V\cup W,\ i<j\}$ is the
                edge set.
                On $E$, a symmentric distance matrix $C=(c_{ij})$
                using Euclidean metric is defined.
                $V$ is the set of nodes that might be visited,
                while $T\subseteq V$ is the set of nodes that must be visited
                starting from a node $s\in T$ and $W$ is the set of
                nodes that must be covered.
                The covering tour problem is an NP-hard problem, consisting
                in finding a minimum length tour or a minimum length 
		Hamiltonian cycle over a subset of $V\cup W$ such that it 
		includes all nodes in $T$ and covers all nodes in $W$.
                This paper presents a {GRASP} to solve the generalized covering
                tour problem, that consists of finding a minimum length tour
                or a minimum length Hamiltonian cycle also through a subset
                of $W$, instead of only a subset of $V$.},
       	year = "2001"
}

@article{OsmAyoBar03a,
        author = {I.H. Osman and B. Al-Ayoubi and M. Barake},
        title = {A greedy random adaptive search procedure for the
                 maximal planar graph problem},
        journal = {Computers and Industrial Engineering},
       volume = {45},
       pages = {635--651},
       annote ={A {GRASP} is proposed and tested for the weighted maximal
                planar graph problem.
                The construction is a randomized version of the Green
                and Al-Hakim algorithm (1985).
                A new data structure is introduced, reducing the complexity
                of the construction from $O(n^3)$ to $O(n^2)$.
                Local search uses four types of moves proposed by Pesch,
                Glover, Bartsch, Salewski, and Osman (1995).},
       year = {2003}
}

@techreport{OsmAyoBarHas00a,
	author = "I.H. Osman and B. Al-Ayoubi and M. Barake and
                  M. Hasan",
	title = "A greedy random adaptive search procedure for the
                 weighted maximal planar graph problem",
	institution = "School of Business and Center for Advanced
                       Mathematical Sciences, American University of
                       Beirut",
	address = "Beirut, Lebanon",
	year = "2000",
	annote = 	"A {GRASP} is proposed and tested for the weighted maximal
              		planar graph problem.
              		The construction is a randomized version of the Green
              		\& Al-Hakim algorithm (1985).
              		A new data structure is introduced, reducing the complexity
              		of the construction from $O(n^3)$ to $O(n^2)$.
              		Local search uses four types of moves proposed by Pesch,
              		Glover, Bartsch, Salewski, and Osman (1995)."	
}

@Article{OsmHasAbd02a,
        author = "I.H. Osman and M. Hasan and A. Abdullah",
        title = "Linear programming based meta-heuristics for the weighted 
		maximal planar graph",
         journal = "Journal of the Operational Research Society",
         volume = "53",
         pages = "1142--1149",
         year = "2002",
        annote   =     "To solve the weighted maximal 
			planar graph problem, two meta-heuristics are 
			described, both derived from an ILP relaxation. 
			The first one takes into account only variables with 
			fractional value greater than half in the ILP 
			relaxation to build an initial subgraph 
			from which a planar subgraph is extracted with the 
			help of a {GRASP} and triangulation of faces. 
			The second approach considers only edges having 
			integer value in the ILP relaxation, while  
			the remaining edges are sorted in descending order of 
			their weights. 
			Those edges that do not violate a planarity test are 
			thus candidate for insertion to obtain a feasible 
			solution using {GRASP}.", 
}

@Article{ParQiaRes99a,
	author = "P.M. Pardalos and T. Qian and M.G.C. Resende",
	title = "A greedy randomized adaptive search procedure for the
		 feedback vertex set problem",
	journal = "Journal of Combinatorial Optimization",
	year = "1999",
	volume = "2",
	pages = "399--412",
        annote   =     "This article describes a {GRASP} for finding
                	approximate solutions to the feedback vertex set problem on
                	a digraph. Several greedy functions are tested, all of them
                	taking into account vertices with high degree.
                	The local search procedure tries at each iteration to
                	eliminate redundant vertices. Some efficient problem
                	reduction techniques are also described. They are useful
                	both to simplify the problem instance and to determine
                	whether a digraph is acyclic or not.",
}

@incollection{ParResRap98a,
	author = "P.M. Pardalos and M.G.C. Resende and J. Rappe",
	title = "An exact parallel algorithm for the maximum clique problem",
	booktitle = "High performance algorithms and software in
                     nonlinear optimization",
	editor = "R. De Leone and A. Murli and P.M. Pardalos and 
		G. Toraldo",
        publisher = "Kluwer Academic Publishers",
        pages = "279--300",
	year = "1998",
	annote   =	"A parallelized version of the exact algorithm of 
			Carraghan and Pardalos (1990) for the unweighted 
			maximum clique problem is described. 
			A variant of the {GRASP} for the maximum independent 
			set problem of Feo, Resende, and Smith (1994) is used 
			for computing feasible solutions."
}

@Article{Res98a,
	author = "M.G.C. Resende",
	title = "Computing approximate solutions of the
		 maximum covering problem using {GRASP}",
	journal = "Journal of Heuristics",
	volume = "4",
        pages = "161--171",
	year = "1998",
        annote   =      "A {GRASP} for the maximum covering problem
                	is described.
                	The greedy function is the total weight of the 
			yet-uncovered demand points that become covered after 
			the selection.
                	The local search procedures uses a $2$-exchange 
			neighborhood structure.
                	The {GRASP} is shown to find near optimal solutions.",
}

@Article{ResFeoSmi98a,
	author = "M.G.C. Resende and T.A. Feo and S.H. Smith",
	title = "Algorithm 787: {Fortran} subroutines for
		 approximate solution of
		 maximum independent set problems using {GRASP}",
	journal = "ACM Transactions on Mathematical Software",
	year = "1998",
	volume = "24",
	pages = "386--394",
        annote   =     "This article describes a set of ANSI standard Fortran 77
                	subroutines to find an approximate solution of a maximum
                	independent set problem. The {GRASP} used to produce the
                	solutions is described in Feo, Resende, and 
			Smith (1994).",
}

@Article{ResRib97a,
	author = "M.G.C. Resende and C.C. Ribeiro",
	title = "A {GRASP} for graph planarization",
	journal = "Networks",
	year = "1997",
	volume = "29",
	pages = "173--189",
	annote   = 	"A {GRASP} for the graph planarization problem is
              		described, extending the two-phase heuristic of 
			Goldschmidt and Takvorian ({\em Networks}, v. 24, 
			pp. 69--73, 1994).
              		The implementation of the {GRASP} is described
              		in detail.  Computational experience on a large set of
              		standard test problems is presented.  On almost all
              		test problems considered, the heuristic either
              		matches or finds a better solution than previously
              		described graph planarization heuristics.  In several
              		cases, previously unknown optimal solutions are found."
}

@Article{RibRes99a,
	author = "C.C. Ribeiro and M.G.C. Resende",
	title = "Algorithm 797: {Fortran} subroutines for
		 approximate solution of
		 graph planarization problems using {GRASP}",
	journal = "ACM Transactions on Mathematical Software",
	volume = "25",
	pages = "341--352",
	year = "1999",
        annote   =     "This paper describes a set of Fortran subroutines that
                	implements the {GRASP} for graph planarization
                	of Resende and Ribeiro (1997).",
}

@Article{RibRos02a,
        author = "C.C. Ribeiro and I. Rosseti",
        title = "A parallel {GRASP} for the 2-path network design problem",
        journal = "Lecture Notes in Computer Science",
        volume = "2004",
        pages = "922--926",
        year = "2002",
        annote   =     "Given a connected undirected graph $G(V,E)$, a 
			nonnegative edge weight function 
			$w:\ E\rightarrow {\mathbb R}^+$, 
			and a set $D$ of pairs of origin-destination nodes, the 
			$2$-path network design problem consists in finding a 
			minimum weighted subset of edges $E'\subseteq E$ 
			containing a $2$-path between the extremities of every 
			origin-destination pair in $D$. 
			In this paper, a parallel {GRASP} with path-relinking 
			is proposed for solving this problem.",
}

@Article{RibUchWer02a,
        author = "C.C. Ribeiro and E. Uchoa and R.F. Werneck",
        title = "A hybrid {GRASP} with perturbations
                 for the {Steiner} problem in graphs",
        journal = "INFORMS Journal on Computing",
        volume = "14",
        pages = "228--246",
        year = "2002",
        annote   =     "In this hybrid {GRASP} here proposed for the {Steiner} 
			problem in graphs, the {GRASP} construction phase 
			is replaced by either one of several different 
			construction procedures that apply weight 
			perturbation strategies combining intensification 
			and diversification elements. 
			The local search phase circularly explores two 
			different strategies. 
			The first defines a simple node-based neighborhood 
			structure. 
			The second one uses a key-path-based neighborhood, 
			where a key-node is a {Steiner} node with degree 
			at least three and a key-path is a {Steiner} tree 
			$T$ whose extremities are either terminals of 
			key-node (if there are any, intermediate nodes are 
			{Steiner} node with degree two in $T$). 
			An adaptive path-relinking procedure is at the 
			end used as a post-optimization strategy.",
}

@phdthesis{Ros03a,
        author = "I.C.M. Rosseti",
        title = "Heur\'{\i}sticas para o problema de s\'{\i}ntese de redes
	         a 2-caminhos",
	school = "Department of Computer Science, Catholic University of
                  Rio de Janeiro",
        address = "Rio de Janeiro, Brazil",
	month = "July",
	annote = {Given a connected undirected graph $G=(V,E)$, 
		a nonnegative weight function defined on $V$, and 
		a set $D$ of origin-destination pair, the $2$-path 
		network design problem ($2$PNDP) consists in finding 
		a minimum weighted subset of edges containing a $2$-path 
		between the endpoints of every origin-destination in $D$, 
		where a $2$-path between the pair $(s,t)\in D$ 
		is a sequence of at most two edges connecting $s$ to $t$. 
		For solving $2$PNDP, sequential and parallel heuristics 
		are proposed, included variants and combinations of 
		{GRASP}. In Portuguese.},
        year = "2003"
}