The Core in Max-Loss Non-Centroid Clustering Can Be Empty
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911283716030464 |
|---|---|
| author | Bredereck, Robert Deltl, Eva Kellerhals, Leon Peters, Jannik |
| author_facet | Bredereck, Robert Deltl, Eva Kellerhals, Leon Peters, Jannik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19107 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Core in Max-Loss Non-Centroid Clustering Can Be Empty Bredereck, Robert Deltl, Eva Kellerhals, Leon Peters, Jannik Machine Learning Artificial Intelligence Computer Science and Game Theory 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. |
| title | The Core in Max-Loss Non-Centroid Clustering Can Be Empty |
| topic | Machine Learning Artificial Intelligence Computer Science and Game Theory |
| url | https://arxiv.org/abs/2511.19107 |