Objeto de conferencia
Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
Registro en:
Autor
Gagliardi, Edilma Olinda
Dorzán, María Gisela
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
Institución
Resumen
Globally optimal pseudo-triangulations are di cult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to nd optimal pseudo-triangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWPT since no reference to benchmarks for these problems were found in the literature. We assess through the experimental evaluation the applicability of the ACO metaheuristic for MWPT. Presentado en el X Workshop Agentes y Sistemas Inteligentes Red de Universidades con Carreras en Informática (RedUNCI)