The Core in Max-Loss Non-Centroid Clustering Can Be Empty
This addresses a theoretical gap in clustering algorithms for scenarios where agents' losses are based on maximum distances, showing that stable solutions may not exist, which is incremental as it extends impossibility results to a new objective.
The paper tackles the problem of core stability in non-centroid clustering with a max-loss objective, proving that for k≥3, there exist metric instances where no clustering lies in the α-core for any α<2^(1/5)≈1.148, which is tight for their construction, and they also provide a computer-aided example with a slightly smaller bound in Euclidean space.
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.