DocumentCode :
3171028
Title :
Parallel strategies for a multi-criteria GRASP algorithm
Author :
Vianna, Dalessandro Soares ; Arroyo, José Elias Claudio ; Vieira, Pedro Sampaio ; De Azeredo, Thiago Ribeiro
Author_Institution :
Nucleo de Pesquisa e Desenvolvimento em Informatica, Univ. Candido Mendes, Rio de Janiero, Brazil
fYear :
2005
fDate :
7-11 Nov. 2005
Abstract :
This paper proposes different strategies of parallelizing a multi-criteria GRASP (greedy randomized adaptive search problem) algorithm. The parallel GRASP algorithm is applied to the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem, a vector of costs is defined for each edge of the graph and the goal is to find all the efficient or Pareto optimal spanning trees (solutions). Each process finds a subset of efficient solutions. These subsets are joined using different strategies to obtain the final set of efficient solutions. The multi-criteria GRASP algorithm with the different parallel strategies are tested on complete graphs with n = 20, 30 and 50 nodes and r = 2 and 3 criteria. The computational results show that the proposed parallel algorithms reduce the execution time and the results obtained by the sequential version were improved.
Keywords :
Pareto optimisation; adaptive systems; computational complexity; greedy algorithms; parallel algorithms; randomised algorithms; tree searching; trees (electrical); NP-hard problem; Pareto optimal spanning trees; combinatorial optimization; graph edges; greedy randomized adaptive search problem; multicriteria GRASP algorithm; multicriteria minimum spanning tree problem; parallel algorithm; Cities and towns; Concurrent computing; Cost function; Design optimization; Large-scale systems; Parallel algorithms; Search problems; Telecommunication traffic; Testing; Tree graphs; Parallel GRASP algorithm; minimum spanning tree.; multi-criteria combinatorial optimization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Chilean Computer Science Society, 2005. SCCC 2005. 25th International Conference of the
ISSN :
1522-4902
Print_ISBN :
0-7695-2491-5
Type :
conf
DOI :
10.1109/SCCC.2005.1587873
Filename :
1587873
Link To Document :
بازگشت