Programação matemática e imersões métricas para aproximações em problemas de corte
DOI:
https://doi.org/10.22456/2175-2745.49694Abstract
Neste trabalho, apresentamos um estudo teórico sobre problemas de otimização NP-difíceis de cortes em grafos e o estado da arte de algoritmos de aproximação que fazem uso de técnicas de programação matemática e de espaços métricos. Três problemas de cortes em grafos foram modelados por programas matemáticos inteiros, sendo esses últimos relaxados para admitirem soluções com valores contínuos. A solução desses programas descrevem vetores unitários, para o problema do corte máximo; pontos sobre um (k − 1)-simplexo, para o problema do corte multisseparador mínimo; e uma métrica, para o problema do corte mais disperso. Cada algoritmo apresentado realiza uma tomada de decisão com base na solução do programa matemático.Downloads
Download data is not yet available.
Downloads
Published
2015-05-18
How to Cite
Viertel, S., & Vignatti, A. L. (2015). Programação matemática e imersões métricas para aproximações em problemas de corte. Revista De Informática Teórica E Aplicada, 22(1), 95–118. https://doi.org/10.22456/2175-2745.49694
Issue
Section
Tutoriais