Clustering com outliers e fairness

• Processo: 25/04638-7
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de agosto 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: Cristina Gomes Fernandes
• Beneficiário: João Guilherme Alves Santos
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Algoritmos de aproximação Agrupamento de dados Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Clustering | fairness | k-Center | k-Median | Otimização Combinatória | Algoritmos de aproximação

Resumo

Clustering refere-se a agrupar objetos baseados na sua similaridade e é uma tarefa de aprendizado não supervisionado muito conhecida, utilizada em algoritmos de tomada de decisão que afetam a vida de milhões de pessoas. Dado o potencial impacto desses algoritmos, restrições de fairness são adicionadas para esses problemas para evitar viés externo e garantir equidade nas decisões. O objetivo desse projeto é estudar dois problemas de clustering sob restrições de fairness: os problemas dos k-centros coloridos e das k-medianas coloridas. Esses são problemas de clustering que permitem outliers e têm como objetivo previnir que uma solução escolha, como outliers, majoritariamente pessoas de um grupo específico. Todos esses problemas são de grande interesse prático e são NP-difíceis, existindo, assim, um interesse especial em encontrar bons algoritmos de aproximação para eles. O foco do projeto é investigar algoritmos de aproximação e resultados de inaproximabilidade para essa classe de problemas de clustering, incluindo novos resultados. Essa linha de pesquisa está na área de otimização combinatória e pesquisa operacional. O candidato tem uma excelente base em ciência da computação, especificamente no tema do projeto e em suas linhas de pesquisa.