@inproceedings{b10f86e23d324540893daa3754c250d5,
title = "Improved Approximation Algorithm for Individual Fairness k-Median",
abstract = "The individual fairness k-median problem is a frequently encountered problem in applications involving center location, which generalizes the standard k-median problem by assigning each point a neighborhood radius, allowing connections only to centers within a constant factor of this radius. In this paper, we present a randomized polynomial-time approximation scheme (PTAS) framework with (2+O(ϵ))-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.",
keywords = "approximation algorithm, clustering, k-median",
author = "Di Wu and Qilong Feng and Jinhui Xu and Jianxin Wang",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.; 17th International Conference on Combinatorial Optimization and Applications, COCOA 2024 ; Conference date: 06-12-2024 Through 08-12-2024",
year = "2025",
doi = "10.1007/978-981-96-4445-2\_27",
language = "English",
isbn = "9789819644445",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "324--337",
editor = "Donglei Du and Lu Han and Dachuan Xu",
booktitle = "Combinatorial Optimization and Applications - 17th International Conference, COCOA 2024, Proceedings",
address = "Germany",
}