TCS Journal 2026 Journal Article
Better guarantees for individual fairness k-median
- Di Wu
- Qilong Feng
- Jianxin Wang
• This paper extends and refines the conference version that appeared in Proceedings of the 17th International Conference on Combinatorial Optimization and Applications by strengthening the theoretical analysis and broadening the scope of the results. • First, we include full and detailed proofs for nearly all lemmas and claims that were previously omitted ( Sections 3 - 4 ). • Second, we extend our techniques to the k -means clustering formulation and establish analogous approximation guarantees ( Section 4 ). • Specifically, we show that our dynamic programming approach yields a ( 1 + ε )-approximation algorithm for the individual fairness k -means problem with a fairness violation of at most ( 2 + ε ). The individual fairness k -median problem is a commonly encountered problem in applications involving center location. It generalizes the standard k -median problem by assigning each point a fairness radius, allowing connections only to centers within a constant factor of this radius. In this paper, we present a randomized ( 1 + ϵ ) -approximation algorithm with a ( 2 + ϵ ) -fairness violation for the individual fairness k -median problem, improving upon the previous best approximation ratio of 7. 081 + ϵ and fairness violation of 3. We propose a new dynamic programming approach to deal with the challenges caused by the individual fairness requirements, which is the crucial step in getting the improved ratio.