Approximation Algorithms for Individual Preference Facility Location
摘要
We study the facility location problem in the context of individual fairness to propose the Individual Preference Facility Location (IPFL) problem. In the vanilla facility location problem, the goal is to select a subset of facilities to serve all clients while minimizing total opening and connection costs. IPFL aims to optimize the facility location objective while meeting individual preferences by requiring that each client is served by a facility within its fair radius. The fair radius is defined as the distance between a client and its \( \tau \) -th nearest neighbor, where \(\tau \) is a carefully designed parameter. IPFL balances facility load by opening more facilities in dense areas. However, a few clients may disproportionately affect the final costs or violate the individual preference constraints. To address this, we extend IPFL to its outlier variant, IPFLO, where up to m clients can remain unserved. As our contribution, we provide 2-approximation algorithms for both IPFL and IPFLO using a dual fitting technique.