Por favor, use este identificador para citar o enlazar este ítem: http://ri.ufs.br/jspui/handle/riufs/1708
Tipo de Documento: Artigo
Título : The minimum stabbing triangulation problem: IP models and computational evaluation
Autor : Piva, Breno
Souza, Cid Carvalho de
Fecha de publicación : 2012
Resumen : The minimum stabbing triangulation of a set of points in the plane (mstr) was previously investigated in the literature. The complexity of the mstr remains open and, to our knowledge, no exact algorithm was proposed and no computational results were reported earlier in the literature of the problem. This paper presents integer programming (ip) formulations for the mstr, that allow us to solve it exactly through ip branch-and-bound (b&b) algorithms. Moreover, one of these models is the basis for the development of a sophisticated Lagrangian heuristic for the problem. Computational tests were conducted with two instance classes comparing the performance of the latter algorithm against that of a standard (exact) b&b. The results reveal that the Lagrangian algorithm yielded solutions with minute, and often null, duality gaps for instances with several hundreds of points in small computation times.
Palabras clave : Minimum stabbing triangulation
Algoritmos
Integer programming
Programação linear inteira
ISSN : 0302-9743
Institución / Editorial : Springer Berlin Heidelberg
Citación : PIVA, B.; SOUZA, C. C. The minimum stabbing triangulation problem: IP models and computational evaluation. Lecture Notes in Computer Science, v. 7422, 2012. Disponível em: <http://dx.doi.org/10.1007/978-3-642-32147-4_5>. Acesso em: 16 mar. 2016.
License: © Springer International Publishing AG - Artigo publicado originalmente em: http://dx.doi.org/10.1007/978-3-642-32147-4_5
URI : https://ri.ufs.br/handle/riufs/1708
Aparece en las colecciones: DCOMP - Artigos de periódicos

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
MinimumStabbingTriangulation.pdf158,5 kBAdobe PDFVista previa
Visualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.