Problemas de coberturas justas e máximas

• Processo: 20/16439-5
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de novembro de 2021
• Data de Término da vigência: 30 de setembro de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Zanoni Dias
• Beneficiário: Ana Paula dos Santos Dantas
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Otimização combinatória Algoritmos Pesquisa operacional
• Palavra(s)-Chave do Pesquisador: Cobertura Justa Máxima | Justiça Algorítmica | Otimização Combinatória | pesquisa operacional | Otimização Combinatória

Resumo

Neste projeto, abordamos problemas de cobertura considerando a conceitos de justiça. Dados um conjunto universo U, uma família de subconjuntos S e uma função C de coloração dos elementos de U, dizemos que uma cobertura (X em S) é justa quando a quantidade de elementos cobertos é dividida igualmente entre as classes de cores. Dados também uma função de peso para os elementos de U e um inteiro k, definimos o problema de cobertura justa máxima (FMC), cujo objetivo é encontrar uma cobertura justa de tamanho k, tal que a soma dos pesos dos elementos cobertos seja máxima. Esse problema foi proposto de modo a remediar casos de injustiça algorítmica, em que parte da população pode ser prejudicada quando visamos apenas a maximização dos ganhos. Estudamos o FMC, e algumas variações desse problema, de modo a desenvolver soluções eficientes que possam ser usadas em aplicações como integração de dados e localização de instalações. Para tal, propomos a abordagem desses problemas em três linhas: análise da complexidade computacional; desenvolvimento de algoritmos exatos, aproximados e heurísticas para a resolução de instâncias; e execução de experimentos computacionais com os algoritmos desenvolvidos. (AU)