In this project, we tackle covering problems considering concepts of fairness. Given a universe set U, a family of subsets S, and a coloring function C of the elements from U, we say that a cover (X in S) is fair if the number of covered elements is equally divided between the color classes. Given also a weight function for the elements of U and an integer k, we define the problem of Fair Maximum Covering (fmc), whose objective is to find a fair cover of size k such that the sum of the weights of the covered elements is maximum. This problem was proposed to remedy cases of algorithmic injustice, where part of the population may be harmed when we consider only the maximization of profits. We study the fmc, and a few variations of the problem, to develop efficient solutions that can be used in applications such as Data Integration and Facility Location. For such, we propose to approach these problems in three lines: analysis of computational complexity; development of exact, approximation, and heuristic algorithms; and the execution of computational experiments with the proposed algorithms.
News published in Agência FAPESP Newsletter about the scholarship: