Abstract
Un grafo con signos se caracteriza por tener pesos +1 o -1 en sus aristas, represen- tando relaciones positivas o negativas, respectivamente, entre los vértices que unen. Entre otras aplicaciones, estos grafos se emplean en los problemas pertenecientes a la familia de Sitting Arrangement (SA), en los que el objetivo es relacionar los vérti- ces de un grafo con signos con los de otro grafo sin signos, evitando que aparezcan relaciones negativas en el camino entre dos vértices conectados positivamente. En este trabajo se aborda una variante del problema del SA, denominada Cyclic Min-Max Sitting Arrangement, para la que se proponen tres métodos constructivos y su incorporación en un esquema Greedy Randomized Adaptive Search Proce- dure ( GRASP). Los constructivos propuestos se basan en tres criterios voraces distintos: i) la función objetivo; ii) los cliqués de tamaño máximo; y iii) el criterio propuesto por McAllister en [ 11]. Los métodos son comparados empíricamente con el método que podría considerarse estado del arte para el problema. Los resultados experimentales muestran que la mejor variante GRASP supera sistemáticamente al método previo, en términos de función objetivo y tiempo de ejecución.
Marcos Robles
Artificial Intelligence Phd Student
Marcos Robles graduated in Software Engineering from the Rey Juan Carlos University in 2022. He is working here as a predoctoral researcher focusing in Graph Layout Problems.
Sergio Cavero
Phd in Artificial Intelligence
Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.
Eduardo García Pardo
Full Professor
One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.