Proportional Clustering, the β-Plurality Problem, and Metric Distortion

Leon Kellerhals, Jannik Peters

Abstract

We show that the proportional clustering problem using the Droop quota for $k = 1$ is equivalent to the $\beta$-plurality problem. We also show that the Plurality Veto rule can be used to select ($\sqrt{5} - 2$)-plurality points using only ordinal information about the metric space and resolve an open question of Kalayci et al. (AAAI 2024) by proving that $(2+\sqrt{5})$-proportionally fair clusterings can be found using purely ordinal information.
BibTeX
@article{kellerhals2026proportional,
  author = {Leon Kellerhals and Jannik Peters},
  title = {{Proportional Clustering, the β-Plurality Problem, and Metric Distortion}},
  journal = {Oper. Res. Lett.},
  year = {2026},
  doi = {10.1016/j.orl.2026.107460},
}
Figure