  When selecting locations for a set of facilities, standard clustering
algorithms may place unfair burden on some individuals and neighborhoods. We
formulate a fairness concept that takes local population densities into
account. In particular, given $k$ facilities to locate and a population of size
$n$, we define the "neighborhood radius" of an individual $i$ as the minimum
radius of a ball centered at $i$ that contains at least $n/k$ individuals. Our
objective is to ensure that each individual has a facility within at most a
small constant factor of her neighborhood radius. We present several
theoretical results:
  We show that optimizing this factor is NP-hard; we give an approximation
algorithm that guarantees a factor of at most 2 in all metric spaces; and we
prove matching lower bounds in some metric spaces. We apply a variant of this
algorithm to real-world address data, showing that it is quite different from
standard clustering algorithms and outperforms them on our objective function
and balances the load between facilities more evenly.
