Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering

Lin, Zeyu; Jia, Chaoqi; Guo, Longkun; Chen, Chao

doi:10.24963/ijcai.2026/506

Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering

Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 4545-4553.

https://doi.org/10.24963/ijcai.2026/506

Keywords

Machine Learning: Clustering
AI: Constraint Satisfaction and Optimization
Constraint Satisfaction and Optimization: Constraint optimization problems
AI Ethics, Trust, Fairnes: Fairness and diversity

Abstract

Motivated by the growing importance of fairness in machine learning, fair k-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into m disjoint groups, and the objective is to select k data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair k-center with an approximation ratio of 2.732. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of 4.464. These ratios can be further respectively improved to 2.414 and 3.828 with a runtime exponential on k. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of 4.732, which can be further improved to 4.42, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.

[Agarwal and Procopiuc, 2002] Pankaj K Agarwal and Ce- cilia Magdalena Procopiuc. Exact and Approximation Al- gorithms for Clustering. Algorithmica, 33:201-226, 2002.
[Asuncion and Newman, 2007] Arthur Asuncion and David Newman. UCI Machine Learning Repository, 2007.
[Badanidiyuru et al., 2014] Ashwinkumar Badanidiyuru, Ba- haran Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming Submodular Maximization: Massive Data Sum- marization on the Fly. In Proceedings of the 20th ACM Special Interest Group on Knowledge Discovery and Data Mining (KDD-14), pages 671-680, 2014.
[Bandyapadhyay et al., 2024] Sayan Bandyapadhyay, Zachary Friggstad, and Ramin Mousavi. Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants. Algorithmica, pages 1-18, 2024.
[Bera et al., 2022] Suman K Bera, Syamantak Das, Sainyam Galhotra, and Sagar Sudhir Kale. Fair k-Center Clustering in MapReduce and Streaming Settings. In Proceedings of the 31st ACM Web Conference (WWW-22), pages 1414- 1422, Virtual Event, Lyon, France, 2022.
[Ceccarello et al., 2024] Matteo Ceccarello, Andrea Pietra- caprina, and Geppino Pucci. Fast and Accurate Fair k- Center Clustering in Doubling Metrics. In Proceedings of the 33rd ACM Web Conference (WWW-24), pages 756-767, 2024.
[Charikar et al., 1997] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental Clustering and Dynamic Information Retrieval. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC-97), pages 626-635, 1997.
[Charikar et al., 2003] Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better Streaming Algorithms for Clus- tering Problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03), pages 30-39, 2003.
[Chen et al., 2019] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally Fair Clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML-19), pages 1032-1041. PMLR, 2019.
[Chen et al., 2024] Xianrun Chen, Sai Ji, Chenchen Wu, Yicheng Xu, and Yang Yang. An Approximation Algorithm for Diversity-aware Fair k-Supplier Problem. Theoretical Computer Science, 983:114305, 2024.
[Chierichetti et al., 2017] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair Clustering through Fairlets. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS-17), pages 5036-5044, 2017.
[Chiplunkar et al., 2020] Ashish Chiplunkar, Sagar Kale, and Sivaramakrishnan Natarajan Ramamoorthy. How to Solve Fair k-Center in Massive Data Models. In Proceedings of the 37th International Conference on Machine Learning (ICML-20), pages 1877-1886, 2020.
[Feder and Greene, 1988] Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proceed- ings of the twentieth annual ACM symposium on Theory of computing, pages 434-444, 1988.
[Feldman et al., 2015] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasub- ramanian. Certifying and Removing Disparate Impact. In proceedings of the 21th ACM SIGKDD international con- ference on knowledge discovery and data mining (KDD-15), pages 259-268, 2015.
[Gadekar et al., 2025] Ameet Gadekar, Aristides Gionis, and Suhas Thejaswi. Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity In- sights. In Proceedings of the 34th ACM on Web Conference (WWW-25), pages 4458-4469, 2025.
[Gonzalez, 1985] Teofilo F Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical computer science, 38:293-306, 1985.
[Goyal and Jaiswal, 2023] Dishant Goyal and Ragesh Jaiswal. Tight FPT Approximation for Constrained k-Center and k-Supplier. Theoretical Computer Science, 940:190-208, 2023.
[Grünbaum et al., 1967] Branko Grünbaum, Victor Klee, Micha A Perles, and Geoffrey Colin Shephard. Convex Polytopes, volume 16. Springer, 1967.
[Guha, 2009] Sudipto Guha. Tight Results for Clustering and Summarizing Data Streams. In Proceedings of the 12th International Conference on Database Theory (ICDT-09), pages 268-275, 2009.
[Guo et al., 2024] Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, and Minhui Xue. Efficient Constrained k- Center Clustering with Background Knowledge. Proceed- ings of the 38th AAAI Conference on Artificial Intelligence (AAAI-24), 38(18):20709-20717, Mar. 2024.
[Guo et al., 2025] Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, and Minhui Xue. Near-optimal algorithms for instance-level constrained k-center clustering. IEEE Transactions on Neural Networks and Learning Systems, 2025.
[Guo et al., 2026a] Longkun Guo, Chaoqi Jia, and Chao Chen. Fair k-Center Clustering on Massive Social Net- work Data Streams. In Proceedings of the 35th ACM Web Conference (WWW-26), pages 4689-4700, 2026.
[Guo et al., 2026b] Longkun Guo, Zeyu Lin, Chaoqi Jia, and Chao Chen. Improved Streaming Algorithm for Fair k- Center Clustering. In Proceedings of the 40th AAAI Con- ference on Artificial Intelligence (AAAI-26), volume 40, 2026.
[Hochbaum and Shmoys, 1985] Dorit S Hochbaum and David B Shmoys. A Best Possible Heuristic for the k- Center Problem. Mathematics of operations research, 10(2):180-184, 1985.
[Huang et al., 2019] Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for Clustering with Fairness Constraints. Advances in Neural Information Processing Systems, 32, 2019.
[Jia et al., 2026a] Chaoqi Jia, Longkun Guo, Kewen Liao, Zhigang Lu, Chao Chen, and Jason Xue. Approxi- mation Algorithm for Constrained k-Center Clustering: A Local Search Approach. Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI-26), 40(43):36982-36990, Mar. 2026.
[Jia et al., 2026b] Chaoqi Jia, Weihong Wu, Longkun Guo, Zhigang Lu, Chao Chen, and Kok-Leong Ong. Optimized Algorithms for Text Clustering with LLM-Generated Con- straints. Proceedings of the 40th AAAI Conference on Ar- tificial Intelligence (AAAI-26), 40(27):22229-22237, Mar. 2026.
[Jones et al., 2020] Matthew Jones, Huy Nguyen, and Thy Nguyen. Fair k-Centers via Maximum Matching. In Pro- ceedings of the 37th International Conference on Machine Learning (ICML-20), pages 4940-4949. PMLR, 2020.
[Kleindessner et al., 2019] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-Center Cluster- ing for Data Summarization. In Proceedings of the 36th International Conference on Machine Learning (ICML-19), pages 3448-3457. PMLR, 2019.
[Lin et al., 2024] Zeyu Lin, Longkun Guo, and Chaoqi Jia. Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee. In Proceedings of the 28th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD-24), pages 105-117. Springer, 2024.
[Mahabadi and Trajanovski, 2023] Sepideh Mahabadi and Stojan Trajanovski. Core-sets for Fair and Diverse Data Summarization. Advances in Neural Information Process- ing Systems, 36:78987-79011, 2023.
[Matthew McCutchen and Khuller, 2008] Richard Matthew McCutchen and Samir Khuller. Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 165-178, 2008.
[Nagarajan et al., 2020] Viswanath Nagarajan, Baruch Schieber, and Hadas Shachnai. The Euclidean k-Supplier Problem. Mathematics of Operations Research, 45(1):1-14, 2020.
[Shimon et al., 1975] Shimon, Even, R., Endre, and Tarjan. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing, 4(4):507-518, 1975.
[Wu et al., 2023] Xiaoliang Wu, Qilong Feng, Jinhui Xu, and Jianxin Wang. The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations. In Proceedings of the 17th International Workshop on Frontiers in Algorith- mics (FAW-23), pages 225-238. Springer, 2023.
[Zhou et al., 2025] Jianqi Zhou, Zhongyi Zhang, Yinghui Wen, and Jiong Guo. From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Lo- cation Problems. In Proceedings of the 31st International Computing and Combinatorics Conference (COCOON-25), pages 297-310. Springer, 2025.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

Center-based clustering is a typical unsupervised learning technique in machine learning (ML) with a wide range of applications, including data summarization [Gadekar et al., 2025], text analysis [Jia et al., 2026b], and decision-making [Huang et al., 2019]. In particular, the k-center problem aims to minimize the maximum distance from any point to its nearest center and has been extensively studied. In general metric spaces, a tight 2-approximation is achievable [Gonzalez, 1985; Hochbaum and Shmoys, 1985], whereas in Euclidean spaces, it is NP-hard to obtain a polynomial-time approximation with a factor better than 1▷82 [Feder and Greene, 1988].

→Corresponding Author

Many applications have proposed k-center problem with constraints including instance-level constraints [Guo et al., 2024; Guo et al., 2025] for improve the clustering accuracy and fairness constraints to mitigate representation bias [Chierichetti et al., 2017; Bera et al., 2022]. In particular, we focus on data summarization fairness which can limit the number of older messages included in a user's feed digest [Mahabadi and Trajanovski, 2023] or enforce genre diversity in movie recommendations. For data summarization fairness, the dataset S is partitioned into m disjoint groups S = S1 →· · ·→Sm and it requires that at most kl centers be selected from each group Sl. This constraint in the fair k-center ensures balanced representation by sensitive attributes.

Under this fairness setting, there has been significant research interest in improving approximation ratios for the problem across different metrics, such as general metrics [Guo et al., 2026b], Euclidean metrics [Guo et al., 2026a] and doubling metrics [Ceccarello et al., 2024], as well as under different computational models, including the offline setting [Kleindessner et al., 2019; Jones et al., 2020] and the streaming model [Chiplunkar et al., 2020; Lin et al., 2024; Guo et al., 2026b].

Inspired by Nagarajan et al., we recently achieved a (1 + ↑3)-approximation for the Euclidean k-supplier problem, improving over the long-standing factor-3 barrier. In Euclidean space, we combine with both Jones et al. and Guo et al. to design algorithms for the fair k-center problem in the streaming model and achieve a (3 + ↑3 + ω)-approximation guarantee. After that, we further aim to improve the approximation ratio. To this end, we propose the first fixed-parameter tractable (FPT) algorithm for fair k-center in Euclidean space, breaking the existing approximation barrier while handling both online model and offline setting.

1.1 RelatedWork

FPT k-Center under Constraints and Specialized Metrics. Fixed-parameter tractable (FPT) approximation algorithms have been extensively studied for the k-center problem in metrics. Agarwal and Procopiuc gave an approximation scheme with running time O(n log k) + (k◁ω)O(k1→1◁d ) where n is the input size and d is the dimension. More recently, Goyal and Jaiswal established a unified FPT framework for a broad class of constrained k-center problem, obtaining 2-approximation algorithms with runtime kO(k)nO(1) . For constrained variants, Bandyapadhyay et al. obtained a 3-approximation for non-uniform k-center with a runtime 2O(k log k)n2 . Wu et al. further studied fair k-center with outliers and obtained an approximation scheme with runtime f(k↪ z↪ ω) · nO(1) , where f is a computable function depending on k, z and ω, z denotes the maximum number of outliers. For Euclidean spaces, Bandyapadhyay et al. also developed an approximation scheme for Euclidean non-uniform k-center with runtime 2O((k log k)◁ω)dn. For FPT algorithms beyond metric spaces, Zhou et al. studied k-center on general graphs and proposed a 3-approximation algorithm running in O(2ε · n5 ) time as well as a 13-approximation algorithm running in εO(ϑ) · poly(n) where ϑ is the number of vertices participating in triangleinequality violations and ε is the minimum number of vertices whose removal transforms the graph into a metric graph.

Data Summarization Fair k-Center. Fair clustering under group representation constraints, specifically, upper bounds on the number of centers per group, was formalized in the context of data summarization by Kleindessner et al., who gave a 5-approximation for two groups and a (3 · 2m→1 ↓ 1)- approximation for m groups. This was significantly improved by Jones et al., who achieved a 3-approximation for arbitrary m via a reduction to matching. Chen et al. later studied a closely related diversity-aware fair k-supplier problem and also obtained a 5-approximation using maximum matching. These offline results establish 3 as the state-of-the-art approximation ratio in general metrics, and a natural question is whether this barrier can be broken in structured spaces Rd .

However, all known algorithms achieving ratios below 5 are either offline or require multiple passes; none operate in the one-pass streaming regime while exploiting Euclidean geometry or fixed-parameter tractability.

Streaming Algorithms for Fair Clustering. Streaming fair clustering poses additional challenges due to the irrevocable nature of decisions and limited memory. Early work on streaming k-center with outliers [Charikar et al., 2003; Matthew McCutchen and Khuller, 2008] laid foundational techniques, but fairness constraints require more sophisticated summaries. Lin et al. recently proposed a one-pass streaming algorithm for fair k-center achieving a (7 + ω)-approximation, while Chiplunkar et al. gave a two-pass streaming algorithm with ratio 3. By leveraging a ϖ-independent center set and reducing the hardest case to a constrained vertex cover problem, Guo et al. presented a one-pass streaming algorithm that achieved a (5 + ω)-approximation for fair k-center in general metric spaces, improving over the previous 7 + ω bound. For Euclidean space, Guo et al. further improved the approximation ratio to (1+2↑3+ω) ↔ 4▷464. Notably, none of the prior streaming approaches leverage FPT subroutines or geometric coreset constructions to achieve better ratios, leaving a gap between offline Euclidean advances and streaming practice.

To the best of our knowledge, our work is the first to combine FPT techniques, Euclidean geometry, and streaming models to achieve better approximation ratio for fair k-center in a one-pass streaming setting.

1.2 Our Contribution

Motivated by the importance of Euclidean space in machine learning, we propose a suite of parameterized, polynomialtime approximation and streaming algorithms. The contribution can be summarized as follows:

Devise a parameterized approximation algorithm with ratio 1 + ↑3 ↔ 2▷732 and integrate it into the streaming framework to obtain an approximation ratio 1+2↑3+ω ↔ 4▷464 for Euclidean fair k-center. These guarantees can be further improved to 1 + ↑2 ↔ 2▷414 and 1 + 2↑2 + ω ↔ 3▷828, respectively.
Propose a polynomial-time one-pass streaming algorithm for Euclidean fair k-center that uses O(k logϑ) memory and achieves an approximation ratio of 3 + ↑3 + ω ↔ 4▷732 by integrating the milestone algorithm of [Jones et al., 2020], where ϑ is the aspect ratio, defined as the ratio between the maximum and minimum pairwise distances.
Conduct extensive experiments on real-world datasets to evaluate the practical performance of our algorithms, demonstrating that they significantly outperform all stateof-the-art methods in terms of solution quality.

Moreover, with a higher memory complexity of O(h · k log ϑ), the approximation ratio of our streaming algorithm can be further improved to 3 + √2+ 2h ↔ 4▷42 by setting h = 122, which slightly improves upon the state-of-the-art ratio of 4▷464 due to Guo et al..

2 Preliminary

Let S be a finite set of n data points distributed in an Euclidean space, where the distance function d : S ↗ S ↘ R↑0. For a given parameter k ≃ N, the traditional k-center clustering problem seeks to select a set of k centers C ⇐ S such that maxs↓S d(s↪C) is minimized, where d(s↪C) = minc↓C d(s↪ c) denotes the distance from a point s to its nearest center in C.

2.1 Problem Statement

The fair k-center clustering problem extends this by imposing additional fairness constraints. Specifically, the dataset S is divided into m disjoint groups: S = S1 → S2 → · · · → Sm. Each group Sl (l ≃ [m], where [m] = ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦) has an associated upper bound kl on the number of centers that can be selected from it. These constraints ensure that the total number of chosen centers across all groups equals k: ∑ml=1 kl = k. This formulation aims to balance the representation of each group in the final clustering solution, thereby mitigating potential biases and ensuring fairness. Then, the fair k-center clustering problem is to find a center set C satisfying the formulation as follows:

Formula not decoded

We assume that the optimal radius of the fair k-center problem is known as r↗ (i.e., r↗ = maxs↓S d (s↪ C ↗ ) for the optimum center set C ↗ ). Note that we actually do not know the exact value of r↗ . Nevertheless, we devise r↗ following the previous works [Jia et al., 2026a] for the offline algorithm and [Guha, 2009] for the online algorithm.

2.2 ϖ-Independent Center Set in Euclidean Space

A key structural tool in this paper is the ϖ-independent center set, a concept formalized in the streaming setting by [Guo et al., 2026b]. Its definition is as follows:

Definition 1. (ϖ-independent center set) ! ⇐ S is a ϖindependent center set of S, if and only if it satisfies the following two conditions:

For any two points p↪ q ≃ !, the distance between them is larger than ϖ, i.e. d(p↪ q) > ϖ.
For any point p ≃ S, there exists a point q ≃ !, such that d(p↪ q) ⇑ ϖ.

Recall that C ↗ is the optimal center set and r↗ is the optimum radius. Then we have:

Lemma 1. Assume ! ⇐ S is a ϖ-independent center set in Euclidean space. If ϖ = ↑3r↗ , then ♣!♣ ⇑ 2k.

Proof. We first show that the number of points in ! within distance r↗ from each c↗ ≃ C ↗ is at most two. Suppose that there exists a center c↗ with three points c1↪ c2↪ c3 ≃ !. Then we have d(c↗ ↪ ci) ⇑ r↗ for i ≃ ¶1↪ 2↪ 3♦. That is, the circle centered at c↗ with radius r↗ has ¶c1↪ c2↪ c3♦ in its interior. Then, by the geometric property of any inner triangle within a circle, we havemax min

Formula not decoded

where the maximum is attained when all the three points c1↪ c2↪ c3 are exactly on the circle and the distance between any two points equals ↑3r↗ . This contradicts the fact that the distance between any pair of points in ! is strictly greater than ↑3r↗ . So there are at most two points of ! that are within distance r↗ from any c↗ ≃ C ↗ . Therefore, the size of ! is at most 2♣C ↗ ♣ = 2k.

Moreover, when ϖ = 2r↗ , we can prove ♣!♣ ⇑ k similarly.

3 Parameterized and Streaming Algorithms for Euclidean Fair k-Center

In this section, we first show that the ϖ-independent center set can lead to a parameterized approximation algorithm with approximation ratio 1 + ↑3 ↔ 2▷732 in Euclidean space, which is better than 3 for the metric space when requiring a runtime exponential on k. Then, we propose incorporating the parameterized algorithm into the post-processing stage of the streaming framework for fair k-center clustering, achieving an overall approximation ratio of 1 + 2↑3 + ω, which is approximately 4▷464 for small ω. Moreover, we show that the ratio of the offline parameterized approximation algorithm can be further improved to 2▷414, and consequently, the ratio of the streaming algorithm is then improved to 3▷828. The proof of the improvement will be provided in the full version.

3.1 Offline Parameterized Approximation

First, we show that ϖ-independent center sets with ϖ = ↑3r↗ can be employed to derive a parameterized approximation algorithm as ⋃ml=1 !l contains a desirable approximation solution, where !l is a ϖ-independent center set for Sl with ϖ = ↑3r↗ :

Theorem 1. For ϖ = ↑3r↗ , there exists ! ⇐ ⋃ml=1 !l for which the following three conditions hold: (1) for each point s ≃ S, there must exist a point c ≃ ! with d(s↪ c) ⇑ (1 + ↑3)r↗ ; (2) ♣!♣ ⇑ k; (3) ♣! ⇒ Sl♣ ⇑ kl. In other words, there exists ! in ⋃ml=1 !l that is a (1+ ↑3)-approximation solution for the fair k-center problem.

Proof. Let C ↗ be an optimal solution. We first give a method to construct a ! from ⋃ml=1 !l according to C ↗ , and then show that the constructed ! satisfies all three conditions.

For the first, our construction simply proceeds as in the following: for each center c↗ ≃ C ↗ , if c↗ ≃ C ↗ is an element of ⋃ml=1 !l, then add c↗ to !; Otherwise, find group Sl that contains c↗ , and then find a point c ≃ !l which is within ↑3r↗ distance away from c↗ , i.e. with d(c↪ c↗ ) ⇑ ↑3r↗ . So, for each s ≃ S, there must exist c ≃ ! such that d(s↪ c) ⇑ d(s↪ c↗ ) + d(c↗ ↪ c) ⇑ r↗ + ↑3r↗ = (1 + ↑3)r↗ , and Cond. (1) holds. As the construction maps each optimal center c↗ ≃ C ↗ ⇒Sl to one center c ≃ !⇒Sl, Cond. (2) and Cond. (3) hold according to the property of the optimal center set C ↗ .

Based on this existence guarantee, our enumeration-based parameterized algorithm simply proceeds in two stages:

For each group l ≃ [m], compute a ϖ-independent center set !l with ϖ = ↑3r↗ .
Enumerate all the possible center sets C with size bounded by k and satisfying the fairness constraint, and choose C with the smallest radius among all the computed center sets.

Lemma 2. The algorithm above can correctly find ! that satisfies the three conditions of Thm. 1.

Proof. First, we show the algorithm can always output a !, which is, there always exists c ≃ !l with d(c↪ c↗ ) ⇑ ↑3r↗ when c↗ ◁≃ ⋃ml=1 !l and c↗ ≃ Sl. Suppose otherwise, then d(c↗ ↪ c) > ↑3r↗ holds for every c ≃ !l, which indicates that c↗ must be added to !l and arises a contradiction.

Then, we show that all three conditions hold. Cond. (1) immediately holds following the construction of !.

For Cond. (2), we add at most one point (i.e., c or c↗ ) to ! upon one point c↗ ≃ C ↗ (note that the point to be added might already exist in !). So ♣!♣ ⇑ ♣C ↗ ♣ = k and hence condition (2) is true. For condition (3), the algorithm adds a point (either c or c↗ ) of Sl to ! if and only if the processing point c↗ belongs to Sl. That is, we have ♣! ⇒ Sl♣ ⇑ ♣C ↗ ⇒ Sl♣ ⇑ kl holds for each l. This completes the proof.

Theorem 2. The fair k-center problem admits a parameterized approximation algorithm with ratio 1 + ↑3 ↔ 2▷732 and runtime O(2k(1+logm) · mnk2 logn).

Proof. The ratio can be directly derived from Thm. 1. That is because the enumeration can always find a ! satisfying the three conditions as in Thm. 1 if such ! exists; while on the other hand, Thm. 1 claims the existence of such !.

For the runtime, Stage 2 enumerates O ((2mk k )) sets (of k-centers), because there are at most 2mk points in ⋃l↓[m] !l. Moreover, each enumerated set requires O(nk) time to compute its maximum radius, so Stage 2 takes a total runtime O (nk · (2mk k )). By employing Stirling's approximation formulation and via calculation, we get:

Formula not decoded

Then, the total runtime of the parameterized algorithm sums up to O(2k(1+logm) · mnk2 log n). Then by multiplying the factor O(log n) for employing the binary search for not knowing r↗ , we complete the proof of Thm. 2. The detailed proof of Lem. 3 can be found in the full version.

3.2 The Parameterized Approximation in Streams

In this subsection, we introduce the general framework of our parameterized streaming algorithm, there are two stages:

Streaming Stage. Construct a ϖ-independent center set !l for each group Sl upon the stream with ϖ = ↑3r↗ .
Post-streaming Stage. Select centers from ⋃ml=1 !l to construct the desired center set ! by enumeration similar to the offline parameterized approximation algorithm.

Because the enumeration here considers only the points in ⋃l !l rather than in the entire point set S, its compromised performance guarantee can be stated as below:

Lemma 4. The parameterized streaming algorithm consumes a memory of O(k logω ϑ) and achieves an approximation ratio 1 + 2↑3 + ω ↔ 4▷464 for any sufficiently small ω > 0, where ϑ = "◁ϱ is the aspect ratio for " = maxp↪q↓S d(p↪ q) denoting the diameter of S and ϱ = minp↪q↓S↪ p≃=q d(p↪ q) being the minimum pairwise distance.

Proof. We need only to bound the distance from any point s ≃ S to the center set C constructed by the parameterized algorithm. For each input point s ≃ Sl, there must exist a point i ≃ !l such that d(i↪ s) ⇑ ↑3r↗ according to the structure for ϖ-independent center set. If i is added to C, then d(s↪C) ⇑ ↑3r↗ immediately holds. Otherwise, we have i ◁≃ C and will show d(s↪C) ⇑ (1 + 2↑3)r↗ holds. Following Thm. 1, there exists ! ⇐ ⋃l !l, such that for any i ≃ ⋃l !l, d(i↪ !) ⇑ (1 + ↑3)r↗ holds. As C is constructed via enumeration, we have

Therefore, we have

Formula not decoded

This completes the proof.

Algorithm 1: The post-streaming algorithm

Input: A ω-independent center set ! with ω = 2r→ and !i (i → [m]) with ω = ↑3r→ . Output: A center set C. 1 Create a directed graph G(V↪ E) with V = ¶s↪ t♦ and E = ↓; 2 Create vertex set V! with one-to-one mapping to points in !; 3 Create a vertex set Vf with a one-to-one mapping to points in !1↪ ▷ ▷ ▷ ↪ !m; 4 Create a vertex set Vt of size mwith a one-to-one mapping to group indices; 5 Update V ↔ V ↗ V! ↗ Vf ↗ Vt; 6 for each group l → [m] do 7 Add an edge from the vertex corresponding to l in Vt to t with capacity kl; 8 for each a → ! and each f → Vf corresponding to a point in ⋃l↑[m] !l do 9 if d(a↪ f) ↘ (1 + ↑3)r→ then 10 Add an edge from vertex a → V! to vertex f → Vf with capacity 1; 11 Add an edge from vertex f → Vf to the vertex l → Vt (where f → !l) with capacity 1; 12 for each a → ! do 13 Add an edge from s to the vertex for a → V! with capacity 1; 14 Run Dinic's Max-Flow algorithm [Shimon et al., 1975] on G from s to t; 15 if the max flow value equals ♣!♣ then 16 Construct C from the centers corresponding to edges used in the flow; 17 return C; 18 else 19 return infeasible.

Note that, by using the smaller value ϖ = ↑2r↗ , the parameterized approximation ratio in Thm. 2 and the ratio in Lem. 4 can be improved to 1+ ↑2 ↔ 2▷414 and 1+2↑2+ω ↔ 3▷828, respectively.

4 Streaming Euclidean Fair k-Center in Polynomial Runtime

In this section, we present a one-pass streaming algorithm for Euclidean space, where the algorithm employs network flow as a building block, achieving a polynomial runtime and a ratio of 3 + ↑3 + ω ↔ 4▷732.

The key idea of our algorithm is first to construct a ϖindependent center set ! for S with ϖ = 2r↗ (ignoring groups) and for each group l, construct ϖ-independent center set !l with a different ϖ = ↑3r↗ along the stream simultaneously; and then use the ! as the solution except replacing some centers therein using ⋃l !l to satisfy the fairness constraint. In general, our algorithm mainly proceeds in two phases:

(1) Upon the stream, construct m+ 1 independent center sets, including m independent center sets !l for each group Sl (l ≃ [m]) regarding ϖ = ↑3r↗ and an independent center set ! for ϖ = 2r↗ ignoring the group division;

Figure 1: An example of executing Alg. 1 with k = 3, k1 = 2↪ k2 = 1. Let ! = ¶c1↪ c2↪ c3♦ be a ω-independent center set for S ignoring the groups for ω = 2r→ . Assume that !1 = ¶a1↪ a2♦↪ !2 = ¶b1↪ b2♦ are for S1↪ S2 respectively with a different ω = ↑3r→ . Each edge has a default capacity of 1 except the edges entering t.

(2) Select at most k centers from the computed ⋃l !l → !: Construct an auxiliary bipartite graph G where a maximal flow corresponds to a center set that can cover all the data points within the desired radius (3 + ↑3)r↗ .

The auxiliary graph G = (V ; E) for Phase (2) can be constructed as follows:

For the vertices of G, set V = ¶s↪ t♦→V! →Vf →Vt where ¶s↪ t♦ is the set of source and target nodes, V! is a set with a one-to-one mapping to points in !, Vf is a set with a one-to-one mapping to points in ⋃ !l and Vt is a set with a one-to-one mapping to group indices.
We add four kinds of edges of G as follows:
For each a ≃ V!, we add an edge from the source node s to the vertex a with capacity 1.
For each a ≃ V! and each f ≃ Vf , if d(a↪ f) ⇑ (1 + ↑3)r↗ , we add an edge from vertex a to vertex f with capacity 1.
For each f ≃ Vf , we add an edge from vertex f to the vertex l ≃ Vt (where f ≃ !l) with capacity 1.
For each group l ≃ [m], we add an edge from the vertex corresponding to l in Vt to the target node t with capacity kl .

The detailed algorithm is as depicted in Alg. 1 and an example is in Fig. 1.

Lemma 5. In Alg. 1, two conditions hold: (1) The size of each !l↪ l ≃ [m], is less than 2k. (2) The size of ! is less than k.

Proof. According to Lem. 1, ♣!♣ ⇑ k is true and ♣!l♣ ⇑ 2k holds for each l ≃ [m].

Lemma 6. In Alg. 1, for point p ≃ !, if ⇓i ≃ !l↪ d(p↪ i) > (1 + ↑3)r↗ holds where l ≃ [m], there exists no point q ≃ Sl such that d(p↪ q) ⇑ r↗ .

Proof. Suppose that there exists a point q ≃ Sl such that d(p↪ q) ⇑ r↗ . Then, there must exist a point i ≃ !l such that d(q↪ i) ⇑ ↑3r↗ . We have d(p↪ i) ⇑ d(p↪ q) + d(q↪ i) ⇑ r↗ + ↑3r↗ = (1+ ↑3)r↗ , contradicting d(p↪ i) > (1+ ↑3)r↗ .

Lemma 7. There exists a flow of value equal to ♣!♣ in the auxiliary graph G if and only if there exists a center set C ⇐

⋃l !l → ! satisfying the fairness requirement and covering all the points of S within a radius (3 + ↑3)r↗ .

Proof. If there exists a flow of value equal to ♣!♣ in the auxiliary graph G, we need to prove C satisfies: (1) ♣C♣ ⇑ k; (2) ♣C ⇒ Sl♣ ⇑ kl; (3) ⇓s ≃ S↪ d(s↪ C) ⇑ (3 + ↑3)r↗ .

For ♣C♣ ⇑ k, the weight of edge from the vertex a in V! to the vertex f in Vf is 1, that is the exchange is one-to-one, when the C created by the maximal flow algorithm, ♣C♣ = ♣!♣ ⇑ k as ! is an 2r↗ -independent center set for S.

Then, for ♣C ⇒ Sl♣ ⇑ kl, according to Lem. 6, there always exists a feasible flow and the weight of edge from the vertex for l in Vl to t is kl, so ♣C ⇒Sl♣ ⇑ kl.

If there exists a center set C ⇐ ⋃l !l → ! satisfying the fairness requirement and covering all the points of S within a radius (3 + ↑3)r↗ . As ♣C♣ = ♣!♣ ⇑ k, there exists a flow of value equal to ♣!♣ in the auxiliary graph G.

For ⇓s ≃ S↪ d(s↪C) ⇑ (3 + ↑3)r↗ , there are two cases: (1) for each point s ≃ S, there exists a point i ≃ ! such that d(s↪ i) ⇑ 2r↗ and i is added to C, we have d(s↪C) ⇑ d(s↪ i) ⇑ 2r↗ ; (2) for each point s ≃ S, there exists a point i ≃ ! such that d(s↪ i) ⇑ 2r↗ , however, a point j ≃ !l↪ l ≃ [m] replace i to be added to C as d(i↪ j) ⇑ (1 + ↑3)r↗ , then d(s↪ C) ⇑ d(s↪ j) ⇑ d(s↪ i) + d(i↪ j) ⇑ 2r↗ + (1 + ↑3)r↗ = (3 + ↑3)r↗ . That is, there exists a center set C ⇐ ⋃l !l → ! satisfying the fairness requirement and covering all the points of S within a radius (3 + ↑3)r↗ .

Theorem 3. For the center set C created by Alg. 1, we have: (1) ♣C ⇒ Sl♣ ⇑ kl; (2) ♣C♣ ⇑ k; (3) d(s↪C) ⇑ (3 + ↑3)r↗ holds for each s ≃ S. In other word, Alg. 1 achieves the approximation ratio 3 + ↑3 ↔ 4▷732 for the streaming fair k-center problem for general m.

Proof. For Cond. (1), as the construction for graph G, the weight of the edge from the vertex for l in Vl to t is kl, the center set C created by Alg. 1 satisfies ♣C ⇒ Sl♣ ⇑ kl.

For Cond. (3), we bound the distance from any point s ≃ S to C created by Alg. 1. For each point s ≃ S, there are two cases: (1) There exists a point i ≃ ! such that d(s↪ i) ⇑ 2r↗ , and i is added into C as a center, thus d(s↪ C) ⇑ 2r↗ ; (2) There exists a point i ≃ ! such that d(s↪ i) ⇑ 2r↗ , then there exists a point j ≃ !l↪ l ≃ [m], d(i↪ j) ⇑ (1 + ↑3)r↗ and i is replaced by j to add to center set C, we have d(s↪C) ⇑ d(s↪ j) ⇑ d(s↪ i) + d(i↪ j) ⇑ 2r↗ + (1 + ↑3)r↗ = (3 + ↑3)r↗ .

For Cond. (2), first, ♣!♣ ⇑ k holds according to lem. 5, then, the weight of the edge from the vertex a ≃ ! to the vertex f in Vf is 1 and the weight of the edge from the vertex f in Vf to the vertex l in Vl is 1. According to the conservation law of flow in the maximum flow algorithm, ♣C♣ ⇑ k holds.

Following the above theorem, and accounting for the cost of guessing r↗ over the stream, we eventually obtain a streaming algorithm with an approximation ratio (3 + ↑3 + ω) and a memory complexity k logω ϑ by running Alg. 1 for each guessed value of r↗ with binary search. Moreover, by using the smaller threshold ϖ = ↑2r↗ to generate !l during streaming and modifying Alg. 1 accordingly via replacing ↑3r↗ with

Figure 2: Empirical approximation ratio (cost◁r→ ) of our algorithms (indicated by a red underline) compared with other baselines. (Solid colors indicate the offline algorithms' result, whereas hatched boxes represent the results of streaming algorithms.)

↑2r↗ , the approximation ratio can be improved to 4▷42, which slightly improves upon the previous state-of-the-art ratio of 4▷464 [Guo et al., 2026a].

5 Experimental Results

In this section, we evaluate our algorithms on both simulated and real-world datasets, comparing them to three approximation algorithms as baselines. All experiments were averaged over multiple runs, implemented in Python 3.8, and executed on a 12th Gen Intel(R) Core(TM) i9 with 64 GB of RAM. 1

5.1 Experimental Setting

Datasets. Following the approach in previous work [Kleindessner et al., 2019], we used their method to construct a simulated dataset with a known optimal solution for the kcenter problem. In addition, we apply our algorithms to three real-world datasets from UCI [Asuncion and Newman, 2007]: Wholesale, Student and Adult. Following the previous work [Jones et al., 2020; Chen et al., 2019; Guo et al., 2026b], we utilized numeric features for clustering and selected multiple categorical attributes to construct datasets with the fair requirement.

Algorithms. To evaluate our offline parameterized algorithm, which achieves a (1 + ↑3)-approximation ratio (OPA; see Section 3.1), we compare it against two baseline methods: the 5-approximation algorithm [Kleindessner et al., 2019] and the 3-approximation algorithm [Jones et al., 2020].

To assess the clustering quality of our online algorithms for the fair k-center problem, we implement a (1 + 2↑3 + ω)- approximation parameterized streaming algorithm (PSA; see Section 3.2) and an improved algorithm with 1+2↑2+ω ratio (imPSA), and a (3 + ↑3 + ω)-approximation algorithm with polynomial time (denoted as (3 + ↑3)-approx; see Section 4). We compare these approaches with two online baselines: the (7 + ω)-approximation algorithm [Lin et al., 2024] and the (5 + ω)-approximation algorithm [Guo et al., 2026b].

1 Our code can be found in GitHub https://github.com/ChaoqiJia/ FPT EuclideanFairk-Center.

Constraints Settings. Following the fairness principle of disparate impact as outlined by Feldman et al., we restricted the selection to kl data points from the lth group to serve as centers. We then evaluated the clustering quality by varying the parameter m and the fair ratio across these datasets.

Metrics. We use the cost metric, as defined in Section 2, to compare the quality of clustering across the datasets based on their average values. Additionally, we measure runtime in seconds.

5.2 Experimental Analysis

In this subsection, we analyze the approximation ratios and running times of all algorithms on a small simulated dataset by varying the number of groups m, with focus on our proposed offline and streaming methods: (3+ ↑3)-Approx, OPA, PSA, and imPSA. We then compare the algorithms on three real-world datasets in terms of clustering cost. Finally, we evaluate how the clustering cost varies under different fairness requirement ratios.

Approximation Factor. We compare algorithm performance by evaluating the relative solution ratio against the provided optimal radius r↗ on the simulated dataset. The ratio of the evaluation result can be referred to as empirical approximation ratio, and the maximum value represents the worst-case. Our target in this experiment is to validate the approximation factors achieved by our algorithms ((3+ ↑3+ω)- Approx, OPA, PSA and imPSA). In Figure 2, we compared our algorithms with the baselines in the settings of ♣S♣ = 200, k = 9, and increased the number of groups m from 2 to 6.

Across all values of the number of groups m, the offline methods (solid-color boxes) consistently achieve lower empirical approximation ratios than the streaming methods (hatched boxes). This holds even though some offline baselines (e.g., Kleindessner et al.) have weaker theoretical guarantees than PSA ((1 + 2↑3 + ω)-approx) and (3 + ↑3 + ω)-approx, while only imPSA breaks the observation. We attribute the stronger empirical performance of the offline methods to their access to the full dataset, whereas streaming algorithms must operate under strict memory constraints and can only exploit a limited subset of data points. This interpretation is further supported by imPSA, which uses more memory than the other streaming algorithms and correspondingly achieves better empirical performance. In addition, our results report empirical performance averaged over 10 runs on 10 simulated datasets for each group size m; the worst-case instances that drive the theoretical approximation guarantees may not arise in our experiments.

Table 1: Evaluation of clustering cost for fair k-center on real-world datasets.
Algorithms	Approx. Ratio	A-Gender	A-Race	S-Address	S-School	S-Sex	W-Location
OPA	1 + ↑3	-	-	1.356	1.376	1.349	0.633
[Jones et al., 2020]	3	0.212	0.232	1.726	1.668	1.663	0.749
[Kleindessner et al., 2019]	5	0.226	0.226	1.702	1.578	1.834	0.749
imPSA	1 + 2↑2 + ε	-	-	1.502	1.623	1.503	0.595
PSA	1 + 2↑3 + ε	0.243	0.243	1.568	1.779	1.633	0.632
3 + ↑3-Approx	3 + ↑3 + ε	0.234	0.229	1.684	1.832	1.540	0.812
[Guo et al., 2026b]	5 + ε	0.307	0.296	1.834	1.788	1.834	0.844
[Lin et al., 2024]	7 + ε	0.310	0.701	1.823	1.788	1.834	0.911

When we analyze the offline and streaming results separately, the empirical approximation ratios are consistent with the theoretical guarantees: algorithms with smaller approximation factors tend to yield smaller observed ratios, and the results remain well within the corresponding worst-case bounds. This agreement indicates strong alignment between our empirical findings and theoretical analysis. Moreover, the experimental results exhibit a similar trend as we vary the number of groups. This suggests that the empirical performance observed for m = 2 generalizes well to larger values of m.

The parameterized methods (i.e., OPA, PSA and imPSA) generally achieve better empirical approximation ratios compared with the baselines. In particular, OPA (1 + ↑3-Approx) performs best among the offline algorithms, while imPSA (1 + 2↑2-Approx) typically outperforms the generic streaming baselines (Guo et al.; Lin et al.). We reason that the parameterized algorithm spent more time and more memory space optimizing the selection of centers.

Clustering on Real World Datasets. In Table 1, we evaluate clustering cost on three real-world datasets under different fairness group settings, setting the number of centers to k = 1% of the dataset size. Under this setting, the Adult yields a relatively large k (about 300), whereas the Student and Wholesale datasets have k less than 10. Consistent with the simulated data, these algorithms exhibit similar empirical trends across datasets. We attribute the strong performance of our methods in part to the larger pool of available candidate centers. However, we also show that the optimal solution restricted to the candidate center set need not coincide with the best performance on the full dataset, especially when k is large. For instance, (3 + ↑3)-Approx occasionally achieves slightly lower cost than PSA on Adult.

Robustness. In Figure 3, we vary the fairness constraint ratio on the Student dataset using the school attribute. We start from the ratio induced by the data distribution when selecting 10% of the points as centers, which corresponds to a constraint range of 5◁35 in this dataset, and then gradually adjust the ratio until it reaches 35◁5.

Figure 3: Cost of our algorithms (indicated by a red underline) compared with other baselines with the different balanced fair center size.

In Figure 3, we observe that all algorithms are affected by the fairness ratio: the clustering cost increases as the ratio becomes more unbalanced. We attribute this trend to the fact that our methods first construct a candidate center set without using group labels. Thus, when the required center ratio aligns with the dataset's natural group distribution, the candidate set is more likely to cover points from each group in a way that satisfies the fairness constraints, which is also representative of many real-world settings. In contrast, this experiment considers deliberately mismatched ratios that deviate from the data distribution. In this case, the cost increases, but the relative ranking of the algorithms remains similar.

6 Conclusion

In this paper, we first propose a parameterized approximation algorithm with a ratio of 1 + ↑3 ↔ 2▷732 for the offline Euclidean fair k-center clustering problem. By applying this algorithm in the post-streaming processing stage, we obtain a streaming algorithm with a ratio of 1 + 2↑3 + ω ↔ 4▷464. These ratios can be further improved to 1 + ↑2 ↔ 2▷414 and 1 + 2↑2 + ω ↔ 3▷828, respectively. To ensure polynomial running time, we devise another one-pass streaming algorithm that incorporates network flow techniques into the milestone algorithm of [Jones et al., 2020], achieving an approximation ratio of 3+↑3+ω ↔ 4▷732. This ratio can be further improved to 4▷42, improving upon the previous state-of-the-art ratio 4▷464 in Euclidean space due to Guo et al..

Acknowledgments

This work is supported by National Natural Science Foundation of China (No. 12271098) and Key Project of the Natural Science Foundation of Fujian Province (No. 2025J02011).

Zeyu Lin, Chaoqi Jia, Longkun Guo, and Chao Chen. 2026. Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 4545–4553. https://doi.org/10.24963/ijcai.2026/506

@inproceedings{ijcai2026p506,
  title     = {Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering},
  author    = {Lin, Zeyu and Jia, Chaoqi and Guo, Longkun and Chen, Chao},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {4545--4553},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/506},
  url       = {https://doi.org/10.24963/ijcai.2026/506},
}

TY  - CPAPER
TI  - Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering
AU  - Lin, Zeyu
AU  - Jia, Chaoqi
AU  - Guo, Longkun
AU  - Chen, Chao
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 4545
EP  - 4553
DO  - 10.24963/ijcai.2026/506
UR  - https://doi.org/10.24963/ijcai.2026/506
ER  -

[1] [Agarwal and Procopiuc, 2002] Pankaj K Agarwal and Ce- cilia Magdalena Procopiuc. Exact and Approximation Al- gorithms for Clustering. Algorithmica, 33:201-226, 2002.

[2] [Asuncion and Newman, 2007] Arthur Asuncion and David Newman. UCI Machine Learning Repository, 2007.

[3] [Badanidiyuru et al., 2014] Ashwinkumar Badanidiyuru, Ba- haran Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming Submodular Maximization: Massive Data Sum- marization on the Fly. In Proceedings of the 20th ACM Special Interest Group on Knowledge Discovery and Data Mining (KDD-14), pages 671-680, 2014.

[4] [Bandyapadhyay et al., 2024] Sayan Bandyapadhyay, Zachary Friggstad, and Ramin Mousavi. Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants. Algorithmica, pages 1-18, 2024.

[5] [Bera et al., 2022] Suman K Bera, Syamantak Das, Sainyam Galhotra, and Sagar Sudhir Kale. Fair k-Center Clustering in MapReduce and Streaming Settings. In Proceedings of the 31st ACM Web Conference (WWW-22), pages 1414- 1422, Virtual Event, Lyon, France, 2022.

[6] [Ceccarello et al., 2024] Matteo Ceccarello, Andrea Pietra- caprina, and Geppino Pucci. Fast and Accurate Fair k- Center Clustering in Doubling Metrics. In Proceedings of the 33rd ACM Web Conference (WWW-24), pages 756-767, 2024.

[7] [Charikar et al., 1997] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental Clustering and Dynamic Information Retrieval. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC-97), pages 626-635, 1997.

[8] [Charikar et al., 2003] Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better Streaming Algorithms for Clus- tering Problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03), pages 30-39, 2003.

[9] [Chen et al., 2019] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally Fair Clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML-19), pages 1032-1041. PMLR, 2019.

[10] [Chen et al., 2024] Xianrun Chen, Sai Ji, Chenchen Wu, Yicheng Xu, and Yang Yang. An Approximation Algorithm for Diversity-aware Fair k-Supplier Problem. Theoretical Computer Science, 983:114305, 2024.

[11] [Chierichetti et al., 2017] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair Clustering through Fairlets. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS-17), pages 5036-5044, 2017.

[12] [Chiplunkar et al., 2020] Ashish Chiplunkar, Sagar Kale, and Sivaramakrishnan Natarajan Ramamoorthy. How to Solve Fair k-Center in Massive Data Models. In Proceedings of the 37th International Conference on Machine Learning (ICML-20), pages 1877-1886, 2020.

[13] [Feder and Greene, 1988] Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proceed- ings of the twentieth annual ACM symposium on Theory of computing, pages 434-444, 1988.

[14] [Feldman et al., 2015] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasub- ramanian. Certifying and Removing Disparate Impact. In proceedings of the 21th ACM SIGKDD international con- ference on knowledge discovery and data mining (KDD-15), pages 259-268, 2015.

[15] [Gadekar et al., 2025] Ameet Gadekar, Aristides Gionis, and Suhas Thejaswi. Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity In- sights. In Proceedings of the 34th ACM on Web Conference (WWW-25), pages 4458-4469, 2025.

[16] [Gonzalez, 1985] Teofilo F Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical computer science, 38:293-306, 1985.

[17] [Goyal and Jaiswal, 2023] Dishant Goyal and Ragesh Jaiswal. Tight FPT Approximation for Constrained k-Center and k-Supplier. Theoretical Computer Science, 940:190-208, 2023.

[18] [Grünbaum et al., 1967] Branko Grünbaum, Victor Klee, Micha A Perles, and Geoffrey Colin Shephard. Convex Polytopes, volume 16. Springer, 1967.

[19] [Guha, 2009] Sudipto Guha. Tight Results for Clustering and Summarizing Data Streams. In Proceedings of the 12th International Conference on Database Theory (ICDT-09), pages 268-275, 2009.

[20] [Guo et al., 2024] Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, and Minhui Xue. Efficient Constrained k- Center Clustering with Background Knowledge. Proceed- ings of the 38th AAAI Conference on Artificial Intelligence (AAAI-24), 38(18):20709-20717, Mar. 2024.

[21] [Guo et al., 2025] Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, and Minhui Xue. Near-optimal algorithms for instance-level constrained k-center clustering. IEEE Transactions on Neural Networks and Learning Systems, 2025.

[22] [Guo et al., 2026a] Longkun Guo, Chaoqi Jia, and Chao Chen. Fair k-Center Clustering on Massive Social Net- work Data Streams. In Proceedings of the 35th ACM Web Conference (WWW-26), pages 4689-4700, 2026.

[23] [Guo et al., 2026b] Longkun Guo, Zeyu Lin, Chaoqi Jia, and Chao Chen. Improved Streaming Algorithm for Fair k- Center Clustering. In Proceedings of the 40th AAAI Con- ference on Artificial Intelligence (AAAI-26), volume 40, 2026.

[24] [Hochbaum and Shmoys, 1985] Dorit S Hochbaum and David B Shmoys. A Best Possible Heuristic for the k- Center Problem. Mathematics of operations research, 10(2):180-184, 1985.

[25] [Huang et al., 2019] Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for Clustering with Fairness Constraints. Advances in Neural Information Processing Systems, 32, 2019.

[26] [Jia et al., 2026a] Chaoqi Jia, Longkun Guo, Kewen Liao, Zhigang Lu, Chao Chen, and Jason Xue. Approxi- mation Algorithm for Constrained k-Center Clustering: A Local Search Approach. Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI-26), 40(43):36982-36990, Mar. 2026.

[27] [Jia et al., 2026b] Chaoqi Jia, Weihong Wu, Longkun Guo, Zhigang Lu, Chao Chen, and Kok-Leong Ong. Optimized Algorithms for Text Clustering with LLM-Generated Con- straints. Proceedings of the 40th AAAI Conference on Ar- tificial Intelligence (AAAI-26), 40(27):22229-22237, Mar. 2026.

[28] [Jones et al., 2020] Matthew Jones, Huy Nguyen, and Thy Nguyen. Fair k-Centers via Maximum Matching. In Pro- ceedings of the 37th International Conference on Machine Learning (ICML-20), pages 4940-4949. PMLR, 2020.

[29] [Kleindessner et al., 2019] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-Center Cluster- ing for Data Summarization. In Proceedings of the 36th International Conference on Machine Learning (ICML-19), pages 3448-3457. PMLR, 2019.

[30] [Lin et al., 2024] Zeyu Lin, Longkun Guo, and Chaoqi Jia. Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee. In Proceedings of the 28th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD-24), pages 105-117. Springer, 2024.

[31] [Mahabadi and Trajanovski, 2023] Sepideh Mahabadi and Stojan Trajanovski. Core-sets for Fair and Diverse Data Summarization. Advances in Neural Information Process- ing Systems, 36:78987-79011, 2023.

[32] [Matthew McCutchen and Khuller, 2008] Richard Matthew McCutchen and Samir Khuller. Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 165-178, 2008.

[33] [Nagarajan et al., 2020] Viswanath Nagarajan, Baruch Schieber, and Hadas Shachnai. The Euclidean k-Supplier Problem. Mathematics of Operations Research, 45(1):1-14, 2020.

[34] [Shimon et al., 1975] Shimon, Even, R., Endre, and Tarjan. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing, 4(4):507-518, 1975.

[35] [Wu et al., 2023] Xiaoliang Wu, Qilong Feng, Jinhui Xu, and Jianxin Wang. The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations. In Proceedings of the 17th International Workshop on Frontiers in Algorith- mics (FAW-23), pages 225-238. Springer, 2023.

[36] [Zhou et al., 2025] Jianqi Zhou, Zhongyi Zhang, Yinghui Wen, and Jiong Guo. From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Lo- cation Problems. In Proceedings of the 31st International Computing and Combinatorics Conference (COCOON-25), pages 297-310. Springer, 2025.