期刊
THEORETICAL COMPUTER SCIENCE
卷 983, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.114305
关键词
Approximation algorithm; Facility location; k-supplier problem; Fair clustering; Maximum matching
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据