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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximation Algorithms for Individual Preference Facility Location

  • Shuilian Liu,
  • Yicheng Xu,
  • Yong Zhang

摘要

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.