Vera Weil

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center

We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for e…