Resumen
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
Estudiante de Doctorado en Inteligencia Artificial
Marcos Robles se graduó en Ingeniería del Software por la Universidad Rey Juan Carlos en 2022. Trabaja aquí como investigador predoctoral centrado en problemas de embebido de grafos.
Sergio Cavero
Doctor en Inteligencia Artificial
Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.
Eduardo García Pardo
Catedrático de Universidad
Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.