| Processo: | 03/10045-0 |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |
| Data de Início da vigência: | 01 de março de 2004 |
| Data de Término da vigência: | 31 de agosto de 2005 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação |
| Pesquisador responsável: | Carlos Eduardo Ferreira |
| Beneficiário: | Fernando Mario de Oliveira Filho |
| Instituição Sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Assunto(s): | Algoritmos de aproximação Otimização combinatória Combinatória poliédrica Branch-and-cut Problema da árvore de Steiner |
| Palavra(s)-Chave do Pesquisador: | Algoritmos De Aproximacao | Branch-And-Cut | Combinatoria Poliedrica | Otimizacao Combinatoria | Problema De Steiner | Set Cover |
Resumo O problema de Steiner com grupos consiste em, dado um grafo G com custos nas arestas e uma coleção R de grupos de vértices, encontrar um subgrafo de G que conecte pelo menos um vértice de cada grupo de R e que tenha custo mínimo. O problema é NP-difícil por ser uma generalização do problema de Steiner em grafos. Diversos algoritmos de aproximação foram propostos para este problema. Nosso objetivo é implementar estes algoritmos e fazer uma análise empírica da qualidade das soluções que eles fornecem. Para tanto, precisaremos também de um algoritmo exato para o problema que encontre o valor ótimo ou pelo menos bons limitantes inferiores para este valor. Pretendemos também, depois desta análise, incorporar os melhores algoritmos de aproximação em nossa abordagem exata para resolver o problema. (AU) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |