Busca avançada
Ano de início
Entree

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

Processo: 95/08929-9
Linha de fomento: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)

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.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.