Voltar
Artigo Acesso aberto Produção Nacional
BIBTEX RIS

Programação matemática e imersões métricas para aproximações em problemas de corte

2015; Volume: 22; Issue: 1 Linguagem: Português

10.22456/2175-2745.49694

ISSN

2175-2745

Autores

Santiago Viertel, André L. Vignatti,

Tópico(s)

Advanced Graph Theory Research

Resumo

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.

Referência(s)