TY - GEN
T1 - The Fair k-Center with Outliers Problem
T2 - 17th International Joint Conference on Theoretical Computer Science - Frontier of Algorithmic Wisdom, IJTCS-FAW 2023
AU - Wu, Xiaoliang
AU - Feng, Qilong
AU - Xu, Jinhui
AU - Wang, Jianxin
N1 - Publisher Copyright:
© 2023, Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - The fair k-center and k-center with outliers problems are two important variants of the k-center problem in computer science, which have attracted lots of attention. The previous best results for the above two problems are a 3-approximation (ICML 2020) and a 2-approximation (ICALP 2016), respectively. In this paper, we consider a common generalization of the two mentioned variants of the k-center problem, denoted as the fair k-center with outliers (FkCO) problem. For the FkCO problem, we are given a set X of points in a metric space and parameters k and z, where the points in X are divided into several groups, and each point is assigned a color to denote which group it belongs to. The goal is to find a subset C⊆ X of k centers and a set Z of at most z outliers such that C satisfies fairness constraints, and the objective maxx ∈ X \ Zminc ∈ Cd(x, c) is minimized. In this paper, we study the Fixed-Parameter Tractability (FPT) approximation algorithm and polynomial approximation algorithm for the FkCO problem. Our main contributions are: (1) we propose a (1 + ϵ) -approximation algorithm in FPT time for the FkCO problem in a low-dimensional doubling metric space; (2) we achieve a polynomial 3-approximation algorithm for the FkCO problem with the reasonable assumptions that all optimal clusters are well separated and have size greater than z.
AB - The fair k-center and k-center with outliers problems are two important variants of the k-center problem in computer science, which have attracted lots of attention. The previous best results for the above two problems are a 3-approximation (ICML 2020) and a 2-approximation (ICALP 2016), respectively. In this paper, we consider a common generalization of the two mentioned variants of the k-center problem, denoted as the fair k-center with outliers (FkCO) problem. For the FkCO problem, we are given a set X of points in a metric space and parameters k and z, where the points in X are divided into several groups, and each point is assigned a color to denote which group it belongs to. The goal is to find a subset C⊆ X of k centers and a set Z of at most z outliers such that C satisfies fairness constraints, and the objective maxx ∈ X \ Zminc ∈ Cd(x, c) is minimized. In this paper, we study the Fixed-Parameter Tractability (FPT) approximation algorithm and polynomial approximation algorithm for the FkCO problem. Our main contributions are: (1) we propose a (1 + ϵ) -approximation algorithm in FPT time for the FkCO problem in a low-dimensional doubling metric space; (2) we achieve a polynomial 3-approximation algorithm for the FkCO problem with the reasonable assumptions that all optimal clusters are well separated and have size greater than z.
KW - approximation algorithm
KW - fair k-center
KW - k-center
UR - https://www.scopus.com/pages/publications/85171431834
U2 - 10.1007/978-3-031-39344-0_17
DO - 10.1007/978-3-031-39344-0_17
M3 - Conference contribution
AN - SCOPUS:85171431834
SN - 9783031393433
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 225
EP - 238
BT - Frontiers of Algorithmics - 17th International Joint Conference, IJTCS-FAW 2023, Proceedings
A2 - Li, Minming
A2 - Sun, Xiaoming
A2 - Wu, Xiaowei
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 14 August 2023 through 18 August 2023
ER -