Advanced search
Start date

Fair maximum cover problems

Grant number: 20/16439-5
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): November 01, 2021
Effective date (End): September 30, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Zanoni Dias
Grantee:Ana Paula dos Santos Dantas
Home 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


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:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: