Metraipolis › archive › dc_d79efb09f1bb

Exact Sum-of-Radii Clustering under Any Constant Stability — arXiv:2611.03547

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.03547
License (as archived): CC0-1.0
Archived: 2026-11-03T18:59:04.192Z
SHA-256 of the archived text: 245ec858c159d4664ca3b2fed0026c78bddc10f7d3b61421496b62fddff14b17
Stable URL of this page: https://metraipolis.com/documento/dc_d79efb09f1bb

How to cite

Exact Sum-of-Radii Clustering under Any Constant Stability — arXiv:2611.03547 — arXiv (en), https://arxiv.org/abs/2611.03547 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d79efb09f1bb (Metraipolis archive dc_d79efb09f1bb, sha256 245ec858c159d4664ca3b2fed0026c78bddc10f7d3b61421496b62fddff14b17)

BibTeX

@misc{dcd79efb09f1bb,
  title = {Exact Sum-of-Radii Clustering under Any Constant Stability — arXiv:2611.03547},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03547},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d79efb09f1bb; sha256 245ec858c159d4664ca3b2fed0026c78bddc10f7d3b61421496b62fddff14b17},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03547. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<\gamma<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $\gamma>1$, extending Gao and Reyzin's result for $\gamma\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,\gamma]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<\gamma<2$, our algorithm runs in $n^{O((\gamma-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $\gamma>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.03547 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:18:07.755Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).