Eva Deltl

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 collectively underrepresented. One of the central notions of fairness in this setting is the $α$-core. The existence of clusterings in the $(1+\sqrt{2})$-core was established by Chen et al. [2019], who also showed instances where the $α$-core is empty for every $α< 2$. Closing this gap has remained an open problem for seven years. We make progress from the lower-bound side by providing an instance whose $α$-core is empty for every $α< 2.1508$. Our techniques rely on establishing connections between variants of the core, namely the Hare core and the Droop core; reducing the search for optimal empty-core instances to a highly structured family of clustering instances; and using a Mixed Integer Linear Program (MILP) to search for optimal lower-bound instances within this reduced space. Using this framework, we also determine tight bounds for Droop quota clustering instances with a small number of possible candidate centers and a single center to be selected. For each number of centers $m \in \{3,4,5,6\}$, we give the exact threshold $α_m^*$ such that an $α_m^*$-core clustering always exists, while for every $α< α_m^*$ there is an instance with $m$ centers whose $α$-core is empty. Although these values were originally found through computer-aided search, we also provide direct proofs that do not rely on MILP certificates.

Robert Bredereck, Eva Deltl, Leon Kellerhals et al.

We study core stability in non-centroid clustering under the max-loss objective, where each agent's loss is the maximum distance to other members of their cluster. We prove that for all $k\geq 3$ there exist metric instances with $n\ge 9$ agents, with $n$ divisible by $k$, for which no clustering lies in the $α$-core for any $α<2^{\frac{1}{5}}\sim 1.148$. The bound is tight for our construction. Using a computer-aided proof, we also identify a two-dimensional Euclidean point set whose associated lower bound is slightly smaller than that of our general construction. This is, to our knowledge, the first impossibility result showing that the core can be empty in non-centroid clustering under the max-loss objective.