Aspectos algoritmicos e estruturais de submodularidade em jogos e otimização

• Processo: 24/16092-6
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Data de Início da vigência: 29 de setembro de 2025
• Data de Término da vigência: 28 de setembro de 2026
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carla Negri Lintzmayer
• Beneficiário: Carla Negri Lintzmayer
• Pesquisador Anfitrião: Martin Loebl
• Instituição Sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
• Instituição Anfitriã: Charles University in Prague (CU), República Tcheca
• Assunto(s): Algoritmos de aproximação Matemática discreta Otimização combinatória Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Matemática Discreta | Otimização Combinatória | teoria dos grafos | Otimização combinatória

Resumo

Este é um projeto de pesquisa a ser executado na Charles University, sob a supervisão do Prof. Martin Loebl. Nosso principal objetivo é estudar alguns problemas que envolvem a noção de submodularidade, tanto de um ponto de vista algorítmico quanto estrutural. A submodularidade aparece em muitas funções de avaliação e, informalmente, modela contextos em que adicionar mais de algo lhe dá menos benefício extra. Elas aparecem na otimização combinatória, por exemplo, em funções de classificação de matroides, na teoria dos jogos algorítmicos, por exemplo, para modelar funções de avaliação de agentes com retornos decrescentes, ou em aprendizado de máquina, por exemplo, como funções objetivas. O pesquisador responsável visitou o pesquisador anfitrião na Faculdade de Matemática e Física da Charles University por alguns dias em abril de 2024, quando eles começaram o trabalho colaborativo em alguns problemas, tendo este período de pesquisa no exterior em mente. Este projeto descreve esses problemas e alguns relacionados.