Otimização combinatória com cortes em grafos planares

• Processo: 25/06231-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2025
• Data de Término da vigência: 28 de fevereiro de 2027
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Marcel Kenji de Carli Silva
• Beneficiário: Henri Michel França Oliveira
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 23/03167-5 - Combinatória clássica, assintótica, quântica e geométrica, AP.TEM
• Assunto(s): Dualidade Otimização combinatória
• Palavra(s)-Chave do Pesquisador: cobertura fracionária | Cortes | Dualidade | grafos planares | Otimização Combinatória

Resumo

Este é o projeto de pesquisa para o estudante de mestrado Henri Michel França Oliveira, a ser realizado no IME-USP sob a supervisão do Prof. Marcel K. de Carli Silva, de 01/05/2025 a 31/08/2027, incluindo um estágio de pesquisa no exterior (BEPE) na Universidade de Waterloo. O objetivo é determinar se existem algoritmos eficientes para o problema de cobertura fracionária de cortes em grafos planares.A cobertura fracionária de cortes, através da teoria anti bloqueadora de Fulkerson, é o dual do célebre problema MaxCut. Entender problemas duais frequentemente fornece percepções importantes sobre os problemas originais, tornando-os centrais para a otimização combinatória.O candidato estudará o MaxCut através da perspectiva da dualidade anti bloqueadora, seguido por uma investigação de algoritmos eficientes para MaxCut em grafos planares - uma classe fundamental de grafos em que muitos problemas computacionalmente difíceis podem ser resolvidos de maneira eficiente.Baseando-se no recente algoritmo de aproximação para cobertura fracionária de cortes em grafos gerais desenvolvido pelo grupo de pesquisa do orientador, o projeto visa determinar se este problema, assim como o MaxCut, admite algoritmos eficientes em grafos planares.Este estudo permitirá que o estudante aprofunde seus conhecimentos em otimização combinatória, capacitando-o para estudos de doutorado e, simultaneamente, contribuindo para o avanço da compreensão sobre uma questão teórica fundamental. (AU)