Clustering with outliers and fairness

• Grant number: 25/04638-7
• Support Opportunities: Scholarships in Brazil - Master
• Start date: August 01, 2025
• End date: February 28, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: João Guilherme Alves Santos
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

Clustering refers to grouping objects based on similarities and is a widely known unsupervised learning task used in decision-making algorithms that affect the lives of millions of people. Given the potential impact of these algorithms, fairness constraints are added to these problems to avoid external biases and ensure fairness in decisions. The goal of this project is to study two clustering problems under fairness constraints: the colorful k-center and colorful k-median problems. These are clustering problems that allow for outliers, and aim at preventing a solution to choose as outliers mostly people from specific groups. All of these problems are of great interest in practice, and are known to be NP-hard, so there is special interest in the design of good approximation algorithms for them. The focus of this project is on the investigation of existing and new approximation algorithms and inapproximability results for this class of clustering problems. This line of research lies in both combinatorial optimization and operations research. The candidate has an excellent background in computer science in general, and specifically on the theme of the project and the line of research.