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

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
id I19-R120-10915-20893
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Heuristic methods
pseudo-triangulation
minimum weight
computational geometry
ACO
spellingShingle Ciencias Informáticas
Heuristic methods
pseudo-triangulation
minimum weight
computational geometry
ACO
Gagliardi, Edilma Olinda
Dorzán, María Gisela
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
topic_facet Ciencias Informáticas
Heuristic methods
pseudo-triangulation
minimum weight
computational geometry
ACO
description 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.
format Objeto de conferencia
Objeto de conferencia
author Gagliardi, Edilma Olinda
Dorzán, María Gisela
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
author_facet Gagliardi, Edilma Olinda
Dorzán, María Gisela
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
author_sort Gagliardi, Edilma Olinda
title Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
title_short Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
title_full Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
title_fullStr Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
title_full_unstemmed Approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
title_sort approximations on minimum weight pseudo-triangulations using ant colony optimization metaheuristic
publishDate 2009
url http://sedici.unlp.edu.ar/handle/10915/20893
work_keys_str_mv AT gagliardiedilmaolinda approximationsonminimumweightpseudotriangulationsusingantcolonyoptimizationmetaheuristic
AT dorzanmariagisela approximationsonminimumweightpseudotriangulationsusingantcolonyoptimizationmetaheuristic
AT leguizamonmarioguillermo approximationsonminimumweightpseudotriangulationsusingantcolonyoptimizationmetaheuristic
AT hernandezpenalvergregorio approximationsonminimumweightpseudotriangulationsusingantcolonyoptimizationmetaheuristic
bdutipo_str Repositorios
_version_ 1764820465074831360

Ejemplares similares