pith. sign in

arxiv: 2502.10068 · v1 · pith:S7RODBAZnew · submitted 2025-02-14 · 💻 cs.GT

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

classification 💻 cs.GT
keywords pluralityproblembetaclusteringinformationmetricordinalproportional
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.