Texto completo
| |
| Autor(es): |
Fernando Mário de Oliveira Filho
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2005-08-12 |
| Orientador: | Carlos Eduardo Ferreira |
| Resumo | |
Neste trabalho estudamos o problema de Steiner com grupos. Descrevemos o problema, investigamos suas conexões com outros problemas de otimização combinatória e fazemos uma rápida discussão sobre sua complexidade computacional. Apresentamos também alguns algoritmos de aproximação que foram propostos, introduzimos novas técnicas de redução de instâncias, fazemos um extensivo estudo poliédrico e terminamos por apresentar um algoritmo exato para o problema baseado na estratégia branch-and-cut. (AU) | |
| Processo FAPESP: | 03/10045-0 - Implementação e teste de algoritmos de aproximação para o problema de Steiner com grupos |
| Beneficiário: | Fernando Mario de Oliveira Filho |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |