Abstract
The minimum load coloring problem consists of finding a 2-coloring function that assign either a color red or blue to each node of a graph such that the (maximum) load is minimized, i.e., to reduce as much as possible the number of edges with, at least, one endpoint colored in red (symmetrically, in blue). This NP-complete problem arises in Wavelength Division Multiplexing (WDM) technology and it has been used for broadcast WDM networks. In this paper, several procedures based on the Variable Neighborhood Search (VNS) methodology are proposed and compared on a set of random graphs and DIMACS benchmarks. Experimental results show that the proposed VNS variant exhibits a remarkable performance in comparison with the state-of-the-art methods. In particular, our approach achieves the best results in 48 out of 52 considered instances by employing, on average, less than 7 seconds. These results are further confirmed by conducting statistical tests.
Alberto Herrán González
Associate Professor
J. Manuel Colmenar
Full Professor
My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.
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.