WorksComputer Science
Minimum Sum-of-Radii Clustering with Strong and Weak Oracles
Abstract
In the minimum sum of radii (MSR) problem, the input is a set of points in a metric space and a parameter , and the goal is to cover the points by at most balls, each centered at an input point, while minimizing the sum of their radii. We study MSR in the weak-strong oracle model of Bateni, Dharangutte, Jayaram, and Wang (COLT'24), where the metric is unknown and is accessed through two oracles. The answers of the weak oracle are given to us for free: for every pair of points, we receive a distance value that, with probability , is arbitrarily corrupted. Exact distances are available only through costly strong queries, where a strong query on a point reveals its exact distances to all previously strongly queried points, and the goal is to minimize the number of strong queries. For every constant , we give the first polynomial-time algorithm that makes strong point queries and, with high probability, returns an -approximation for MSR; the previously best algorithm required running time and a number of strong queries exponential in . This is within an factor of a lower bound that we prove: any constant-factor approximation that succeeds with high probability on every instance must make strong queries in expectation on some instance. The same lower bound holds for -center, where it matches the known upper bound up to an factor. An optimal MSR cluster can be small both in size and in radius, so a uniform sample of strongly queried points may miss it entirely. Instead, our algorithm uses a packing LP over the balls certified so far to decide which points to query next. The analysis holds against an adversary who knows which pairs are corrupted.