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

被引：0

作者：

Chen, Xianrun ^{[1
]}

Ji, Sai ^{[2
]}

Wu, Chenchen ^{[3
]}

Xu, Yicheng ^{[1
]}

Yang, Yang ^{[1
]}

机构：

[1] Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China

[2] Hebei Univ Technol, Inst Math, Tianjin 300401, Peoples R China

[3] Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2024年 / 983卷

关键词：

Approximation algorithm; Facility location; k-supplier problem; Fair clustering; Maximum matching;

D O I：

10.1016/j.tcs.2023.114305

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页数：7

共 50 条

[1] The Euclidean k-Supplier Problem
Nagarajan, Viswanath
Schieber, Baruch
Shachnai, Hadas
MATHEMATICS OF OPERATIONS RESEARCH, 2020, 45 (01) : 1 - 14
[2] The Euclidean k-Supplier Problem in IR2
Basappa, Manjanna
Jallu, Ramesh K.
Das, Gautam K.
Nandy, Subhas C.
ALGORITHMS FOR SENSOR SYSTEMS (ALGOSENSORS 2016), 2017, 10050 : 129 - 140
[3] Diversity-Aware k-median: Clustering with Fair Center Representation
Thejaswi, Suhas
Ordozgoiti, Bruno
Gionis, Aristides
MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2021: RESEARCH TRACK, PT II, 2021, 12976 : 765 - 780
[4] The Euclidean k-supplier problem in IR2
Basappa, Manjanna
Jallu, Ramesh K.
Das, Gautam K.
Nandy, Subhas C.
OPERATIONS RESEARCH LETTERS, 2021, 49 (01) : 48 - 54
[5] An approximation algorithm to the k-Steiner Forest problem
Zhang, Peng
Xia, Mingji
THEORETICAL COMPUTER SCIENCE, 2009, 410 (11) : 1093 - 1098
[6] A new approximation algorithm for the k-facility location problem
Zhang, Peng
THEORETICAL COMPUTER SCIENCE, 2007, 384 (01) : 126 - 135
[7] Approximation algorithm for the k- product uncapacitated facility location problem
Yi, Bin
Li, Rongheng
PROCEEDINGS OF 2010 3RD IEEE INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (ICCSIT 2010), VOL 5, 2010, : 602 - 605
[8] An approximation algorithm for the k-level stochastic facility location problem
Wang, Zhen
Du, Donglei
Gabor, Adriana F.
Xu, Dachuan
OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 386 - 389
[9] An Approximation Algorithm for the Dynamic k-level Facility Location Problem
Wang, Limin
Zhang, Zhao
Xu, Dachuan
Zhang, Xiaoyan
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019, 2019, 11640 : 284 - 291
[10] An approximation algorithm for the Generalized k-Multicut problem
Zhang, Peng
Zhu, Daming
Luan, Junfeng
DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) : 1240 - 1247

← 1 2 3 4 5 →