Approximated algorithms for the Minimum Dilation Triangulation Problem
| Autor: | Gregorio Hernández-Peñalver, María Gisela Dorzán, Mario Guillermo Leguizamón, Efrén Mezura-Montes |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Mathematical optimization
Control and Optimization Computer Networks and Communications Iterated local search Management Science and Operations Research Dilation (operator theory) Operator (computer programming) Artificial Intelligence MINIMUM DILATION Local search (optimization) COMPUTATIONAL GEOMETRY Metaheuristic Mathematics business.industry Triangulation (social science) Computational geometry METAHEURISTICS TRIANGULATION Ciencias de la Computación Ciencias de la Computación e Información Simulated annealing business Algorithm Software CIENCIAS NATURALES Y EXACTAS Information Systems |
| Popis: | The complexity status of the Minimum Dilation Triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the Sequential Parameter Optimization Toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator. Fil: Dorzán, Maria Gisela. Universidad Nacional de San Luis; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico San Luis; Argentina Fil: Leguizamon, Mario Guillermo. Universidad Nacional de San Luis; Argentina Fil: Mezura Montes, Efrén. Universidad Veracruzana; México Fil: Hernández Peñalver, Gregorio. Universidad Politecnica de Madrid; España |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|