Busca avançada
Ano de início
Entree

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)