Resolução exata do problema da triangulação de custo mínimo: uma abordagem de programação linear inteira

• Processo: 95/08929-9
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Vigência (Início): 01 de março de 1996
• Vigência (Término): 30 de abril de 1997
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Aminadab Pereira Nunes
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Combinatória poliédrica Geometria computacional Programação linear inteira Triangulação (geometria)
• Palavra(s)-Chave do Pesquisador: Combinatoria Poliedrica | Geometria Computacional | Programacao Linear Inteira | Trinagulacao Custo Minimo

Resumo

Este projeto trata do problema da triangulação de custo mínimo (PTCM). Apesar de ser um problema clássico em geometria computacional, o PTCM permanece com sua complexidade desconhecida. Usualmente este problema é resolvido de forma aproximada. Discutiremos neste projeto a possibilidade de resolução exata deste problema utilizando técnicas de programação linear inteira, em particular, através de algoritmos de Branch-AMD-CUT. Além disso, mostramos uma certa equivalência entre o PTCM e o problema do conjunto independente, e comentamos como esta equivalência pode ser útil a este projeto. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

NUNES, Aminadab Pereira. Uma abordagem de programação inteira para o problema da triangulação de custo minimo. 1997. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.