GRASP for the SumCut Problem

Jesús Sánchez-Oro, Abraham Duarte
January, 2011
Cite

Abstract

This paper proposes a GRASP algorithm 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, … , !, 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 Genoma 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.

Type
Conference paper
Publication
17textsuperscriptth International Congress on Computer Science Research
Jesús Sánchez-Oro
Jesús Sánchez-Oro
Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.

Abraham Duarte
Abraham Duarte
Full Professor

Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.