Approximations on Minimum Weight Pseudo-triangulation Problem Using Ant Colony Optimization Metaheuristic

In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. Globally optimal pseudo-triangulations with respect to the weight, as optimization criteria, are difficult to be found by deterministic methods, since no polynomial algorithm is...

Full description

Saved in:
Bibliographic Details
Main Authors: Gagliardi, E. O., Dorzan, M. G., Leguizamon, M. G., Penalver, G. H.
Format: Conference Proceeding
Language:English
Subjects:
ACO Metaheuristic
Algorithm design and analysis
Approximation algorithms
Approximation methods
Computational Geometry
Face
Minimum Weight
Optimization
Partitioning algorithms
Probabilistic logic
Pseudo-Triangulation
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. Globally optimal pseudo-triangulations with respect to the weight, as optimization criteria, are difficult to be found by deterministic methods, since no polynomial algorithm is known. We show how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality pseudo-triangulations of minimum weight. We present the experimental and statistical study based on our own set of instances since no reference to benchmarks for these problems were found in the literature. Throughout the experimental evaluation, we appraise the ACO metaheuristic performance for MWPT problem.
ISSN:1522-4902
2691-0632
DOI:10.1109/SCCC.2011.31