O problema da árvore de Steiner com coleta de prêmios

• Processo: 20/10341-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2020
• Data de Término da vigência: 31 de julho de 2021
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carlos Eduardo Ferreira
• Beneficiário: Gabriel Morete de Azevedo
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Problema da árvore de Steiner Algoritmos Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Árvore de Steiner | Otimização Combinatória | otimização inteira | teoria dos grafos | Otimização Combinatória

Resumo

Este é um projeto de Iniciação Científica com duração de doze meses que ocorrerá de 01/08/2020 a 30/07/2021, no Instituto de Matemática e Estatística da USP. Nesse projeto, propõe-se o estudo do problema da árvore de Steiner com coleta de prêmios, uma generalização do problema da árvore de Steiner que possui diversas aplicações práticas. No decorrer do projeto o aluno estudará formulações, algoritmos exatos e aproximações para o problema publicados em trabalhos recentes. Além disso, aluno estudará tópicos teóricos de otimização combinatória, dentre os quais temos projeto de algoritmos, classes de complexidade e inaproximabilidade.