We introduce Individual Preference Facility Location (IPFL), a variant of uncapacitated facility location that captures heterogeneous service requirements via local density. Fix a threshold \(\tau \ge 1\) . Each client j is assigned a personalized fair radius \(r_{j,\tau }\) , defined as the distance from j to its \((\tau -1)\) -th nearest client, and IPFL requires assigning every client to an opened facility within its own radius \(r_{j,\tau }\) . Assuming feasibility, we develop a 2-approximation algorithm for IPFL based on a two-stage framework: we first construct a restricted edge set, and then run a dual-fitting algorithm on the restricted instance, while preserving the approximation guarantee for the original problem. We further leverage the Lagrangian-relaxation connection between facility location and k-median, and use our IPFL algorithm as a subroutine to obtain a (4, 2)-bicriteria approximation for the individually fair k-median problem with respect to \((\text {cost}, \text {fairness violation})\) . We also study two natural relaxations: IPFL with outliers (IPFLO), where up to m clients may be excluded, and IPFL with penalties (IPFLP), where client j may be dropped by paying a penalty \(\pi _j\) . For both variants, we obtain polynomial-time 2-approximation algorithms.
