Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gagliardi, Edilma Olinda, Dorzán, María Gisela, Leguizamón, Mario Guillermo, Hernández Peñalver, Gregorio
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2009
Materias:
Ciencias Informáticas
Heuristic methods
pseudo-triangulation
minimum weight
computational geometry
ACO
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/20893
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
Descripción
Sumario: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.

Ejemplares similares