Metaheuristic approaches for MWT and MWPT problems

It is known that the Minimum Weight Triangulation problem is NP-hard. Also the complexity of Minimum Weight Pseudo-Triangulation problem is unknown, suspecting that it is also a NP-hard problem. Therefore we focused on the development of approximate algorithms to find high quality triangulations an...

Descripción completa

Detalles Bibliográficos
Autores principales: Dorzán, María Gisela, Gagliardi, Edilma Olinda, Hernández Peñalver, Gregorio, Leguizamón, Mario Guillermo
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2011
Materias:
Ciencias Informáticas
Heuristic methods
Computational Geometry and Object Modeling
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/18640
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-18640
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
Computational Geometry and Object Modeling
spellingShingle Ciencias Informáticas
Heuristic methods
Computational Geometry and Object Modeling
Dorzán, María Gisela
Gagliardi, Edilma Olinda
Hernández Peñalver, Gregorio
Leguizamón, Mario Guillermo
Metaheuristic approaches for MWT and MWPT problems
topic_facet Ciencias Informáticas
Heuristic methods
Computational Geometry and Object Modeling
description It is known that the Minimum Weight Triangulation problem is NP-hard. Also the complexity of Minimum Weight Pseudo-Triangulation problem is unknown, suspecting that it is also a NP-hard problem. Therefore we focused on the development of approximate algorithms to find high quality triangulations and pseudo-triangulations of minimum weight. In this work we propose the use of two metaheuristics to solve these problems: Ant Colony Optimization (ACO) and Simulated Annealing (SA). For the experimental study we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were found in the literature. Through the experimental evaluation, we assess the applicability of the ACO and SA metaheuristics for MWT and MWPT problems. These results are compared with those obtained from the application of deterministic algorithms for the same problems (Delaunay Triangulation for MWT and a Greedy algorithm respectively for MWT and MWPT).
format Objeto de conferencia
Objeto de conferencia
author Dorzán, María Gisela
Gagliardi, Edilma Olinda
Hernández Peñalver, Gregorio
Leguizamón, Mario Guillermo
author_facet Dorzán, María Gisela
Gagliardi, Edilma Olinda
Hernández Peñalver, Gregorio
Leguizamón, Mario Guillermo
author_sort Dorzán, María Gisela
title Metaheuristic approaches for MWT and MWPT problems
title_short Metaheuristic approaches for MWT and MWPT problems
title_full Metaheuristic approaches for MWT and MWPT problems
title_fullStr Metaheuristic approaches for MWT and MWPT problems
title_full_unstemmed Metaheuristic approaches for MWT and MWPT problems
title_sort metaheuristic approaches for mwt and mwpt problems
publishDate 2011
url http://sedici.unlp.edu.ar/handle/10915/18640
work_keys_str_mv AT dorzanmariagisela metaheuristicapproachesformwtandmwptproblems
AT gagliardiedilmaolinda metaheuristicapproachesformwtandmwptproblems
AT hernandezpenalvergregorio metaheuristicapproachesformwtandmwptproblems
AT leguizamonmarioguillermo metaheuristicapproachesformwtandmwptproblems
bdutipo_str Repositorios
_version_ 1764820463146500098

Ejemplares similares