Improved Lower Bounds for Proportionally Fair Clustering

Benjamin Cookson, Eva Deltl, Yeeseok Oh

We study proportionally fair clustering, where a set of $k$ centers must be chosen from a metric space to represent $n$ agents, and no sufficiently large group of agents should be…