An approximation algorithm for diversity-aware fair k-supplier problem

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.

Automated summary

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.