Grasp with path relinking for the sumcut problem

Resumen

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 set1,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, because a solution for SumCut is reversal solution for Profile problem. 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.

Jesús Sánchez-Oro

Profesor Titular de Universidad

Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.