VNS pour le Minimum Sitting Arrangement Problem

Abstract

Les graphes signés sont des graphes pour lesquels les arêtes ont un signe positif ou négatif. En psychologie sociale, les graphes signés modélisent des relations sociales. Les arêtes positives présentent alors l’amitié et les arêtes négatives les inimitiés entre les nœuds qui représentent les personnes. Dans un travail récent, Kermarrec et al. ont formalisé le problème suivant : « Est il possible de dessiner un graphe signé tel que pour toutes personnes, ses amis sont plus proches que ses ennemis ? ». Lorsque l’on se limite au dessin dans un espace euclidien de taille 1 (sur une ligne), le problème dans le cas général est NP-Complet.

Eduardo García Pardo

Associate Professor

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.

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.