arXiv preprint ·
$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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-δ$ 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 $Ω(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
Limits and Constants of OpenAI's Claimed ETH Refutation
Traveling Salesman Problem on Graphs with Proportional Independent Set
Facility Location with Customer Incompatibilities
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.