证明了最大损失聚类中核心可能为空，且存在严格下界。
The Core in Max-Loss Non-Centroid Clustering Can Be Empty
- 在最大距离损失下，构造反例证明核心可空
- 当k≥3时，α<1.148时无稳定聚类解
- 首次揭示非中心聚类的核心空集可能性
我们研究在最大损失目标下的非中心聚类中的核心稳定性，其中每个参与者的损失是其到所属簇内其他成员的最大距离。证明了对所有k≥3，存在满足n≥9且n被k整除的度量空间实例，使得对于任意α<2^(1/5)≈1.148，不存在任何聚类位于α-核心中。该界限对我们的构造是紧的。通过计算机辅助证明，我们还找到了一个二维欧几里得点集，其对应的下界略低于一般构造的结果。据我们所知，这是首个关于最大损失目标下非中心聚类核心可能为空的不可能性结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。