betaFeedback

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 nn points in a metric space and a parameter kk, and the goal is to cover the points by at most kk 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 δ<1/2δ< 1/2, we give the first polynomial-time algorithm that makes O(klog⁡nlog⁡log⁡n)O(k \log n \log\log n) strong point queries and, with high probability, returns an O(1)O(1)-approximation for MSR; the previously best algorithm required running time and a number of strong queries exponential in kk. This is within an O(log⁡log⁡n)O(\log\log n) factor of a lower bound that we prove: any constant-factor approximation that succeeds with high probability on every instance must make Ω(klog⁡n)Ω(k \log n) strong queries in expectation on some instance. The same Ω(klog⁡n)Ω(k \log n) lower bound holds for kk-center, where it matches the known upper bound up to an O(log⁡log⁡n)O(\log\log n) 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.

Paper details

vlnc:W_bxjxnqz4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…