DocumentCode :
579038
Title :
Approximations on Minimum Weight Pseudo-triangulation Problem Using Ant Colony Optimization Metaheuristic
Author :
Gagliardi, E.O. ; Dorzan, M.G. ; Leguizamon, M.G. ; Penalver, G.H.
Author_Institution :
Fac. de Cienc. Fis. Mat. y Naturales, Univ. Nac. de San Luis, San Luis, Argentina
fYear :
2011
fDate :
9-11 Nov. 2011
Firstpage :
238
Lastpage :
246
Abstract :
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.
Keywords :
ant colony optimisation; polynomial approximation; ACO; MWPT; ant colony optimization metaheuristic; deterministic methods; minimum weight pseudo triangulation problem approximations; polynomial algorithm; Algorithm design and analysis; Approximation algorithms; Approximation methods; Face; Optimization; Partitioning algorithms; Probabilistic logic; ACO Metaheuristic; Computational Geometry; Minimum Weight; Pseudo-Triangulation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science Society (SCCC), 2011 30th International Conference of the Chilean
Conference_Location :
Curico
ISSN :
1522-4902
Print_ISBN :
978-1-4673-1364-3
Type :
conf
DOI :
10.1109/SCCC.2011.31
Filename :
6363403
Link To Document :
بازگشت