Algoritmos lagrangeanos para o problema da árvore geradora de dilatação mínima em um grafo geométrico

• Processo: 11/07929-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de julho de 2011
• Vigência (Término): 30 de junho de 2012
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Alex Fernando Brandt
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Geometria computacional Otimização combinatória Relaxação Lagrangeana
• Palavra(s)-Chave do Pesquisador: Geometria Computacional | Grafos de dilatação mínima | Limitantes duais | Otimização Combinatória | relaxação lagrangeana | Algoritmos em grafos geométricos

Resumo

Este projeto de Iniciação Científica tem por objetivo estudar a aplicação da Relaxação Lagrangeana ao Problema da Árvore Geradora de Dilatação Mínima em Grafos Geométricos (PAGDMGG) visando encontrar limitantes primais e duais para o valor ótimo. Esse problema tem como entrada um conjunto de pontos P no plano. Define-se, então, o grafo geométrico G(P) associado a P como sendo o grafo não-direcionado, ponderado e completo com n vértices, onde o peso de uma aresta corresponde à distância euclidiana entre os pontos representados por suas extremidades. O objetivo é encontrar uma árvore geradora T de G(P) que minimize a maior razão entre os comprimentos do caminho mais curto em T e em G(P) para todo par de vértice do grafo, medida essa chamada de dilatação de T. O fato do PAGDMGG ser NP-Difícil justifica o uso de Relaxação Lagrangeana para obtenção de limitantes para o valor ótimo. Esses limitantes podem ser usados na avaliação de outros métodos de solução propostos para o problema como, por exemplo, heurísticas. (AU)