Metraipolis › archive › dc_cd516171eb56
$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering — arXiv:2611.00461
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00461
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:34.784Z
- SHA-256 of the archived text
f791c9ad008363904ce968224dd18fea010c633ac46f2474eb9fe972583db4c2- Stable URL of this page
https://metraipolis.com/documento/dc_cd516171eb56
How to cite
$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering — arXiv:2611.00461 — arXiv (en), https://arxiv.org/abs/2611.00461 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd516171eb56 (Metraipolis archive dc_cd516171eb56, sha256 f791c9ad008363904ce968224dd18fea010c633ac46f2474eb9fe972583db4c2)
BibTeX
@misc{dccd516171eb56,
title = {$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering — arXiv:2611.00461},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00461},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd516171eb56; sha256 f791c9ad008363904ce968224dd18fea010c633ac46f2474eb9fe972583db4c2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00461. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the weak-strong distance oracle model of Bateni, Dharangutte, Jayaram and Wang (COLT 2024), a metric $(X,d)$ on $n$ points is accessed through two oracles: a cheap weak oracle that returns each queried distance correctly with probability $1-\delta$ and permits arbitrary values on corrupted pairs, chosen by an adversary who knows the entire metric and all corrupted pairs, and an expensive strong oracle that reveals a point exactly. The goal is to cluster well while making as few strong queries as possible. Our main result is a $(6+\varepsilon)$-approximation for $k$-center using $O(k\log n\log(\varepsilon^{-1}\log n))$ strong point queries, for any fixed $\varepsilon>0$. This improves both the $(14+\varepsilon)$ approximation factor and the $O(k\log^2 n\log(\varepsilon^{-1}\log n))$ query bound of Bateni et al. It also improves the query complexity of the recent $(6+\varepsilon)$-approximation of Pradhan, Bhattacharya and Jaiswal (AISTATS 2026), in the variant of the model they study. Our algorithm outputs an explicitly known sketch of an otherwise unknown metric: a concrete metric on at most $k$ points that a downstream algorithm can compute with directly, with no further queries and no noise. As an application, we give a simple FPT algorithm for Minimum Sum of Radii (MSR) that returns a constant-factor solution using $2^{O(k\log k)}\cdot O(\log n\log\log n)$ strong queries. We complement the upper bound with an $\Omega(k\log(n/k))$ lower bound for $k$-center with assignment that holds for row-local algorithms. These algorithms assign two unqueried points to the same center whenever their weak distances to the strong-queried points are exactly the same. Our algorithm and those of Bateni et al. and Pradhan et al. are all row-local, so our query bound is optimal for this class up to the $O(\log\log n)$ factor.
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.00461 — 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-03T11:07:52.223Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).