GRASP with Path Relinking for the SumCut Problem.

TitleGRASP with Path Relinking for the SumCut Problem.
Publication TypeNon-indexed journals
Year of Publication2012
AuthorsSánchez-Oro, J., and A. Duarte

This paper proposes a GRASP algorithm combined with Path Relinking to solve the SumCut minimization problem. In the SumCut problem one is given a graph with n nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2, ...n} in order to minimize the sum cut of the generated solution. The SumCut problem is really important in archeology (in seriation tasks) and in genetics, helping in the Human Genome Project. This problem is equivalent to the Profile problem, but giving the reverse solution. Both problems are graph layout problems, and they are equivalent, because a solution for SumCut is reversal solution for Profile problem. This paper will solve only the SumCut problem, so in order to obtain a solution for the Profile problem it is only need to reverse the given solution. Experimental results show that the GRASP and Path Relinking methods presented outperform in terms of average percentage deviation the results from the State of the Art using shorter CPU time.

Full text: