Journal
THEORETICAL COMPUTER SCIENCE
Volume 983, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.114305
Keywords
Approximation algorithm; Facility location; k-supplier problem; Fair clustering; Maximum matching
Categories
Ask authors/readers for more resources
This paper introduces the diversity-aware fair k-supplier problem and presents an efficient 5-approximation algorithm to address the fairness and over-representation issues in facility selection.
In this paper, we introduce the diversity-aware fair k-supplier problem, which involves selecting k facilities from a set F that consists of m disjoint groups, subject to a constraint on the maximum number of facilities selected from each group. The goal is to ensure fairness in the selection process and avoids any demographic group from over-representation. While the classical k -supplier problem is known to be NP-hard to solve and is even NP-hard to approximate within a factor of less than 3, we present an efficient 5-approximation algorithm for the diversity-aware k-supplier problem based on maximum matching.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available