Fair maximum cover problems

• Grant number: 20/16439-5
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: November 01, 2021
• End date: September 30, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Ana Paula dos Santos Dantas
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

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. (AU)