Metric Clustering and MST with Strong and Weak Distance Oracles

MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram +1

We study optimization problems in a metric space $(\mathcal{X},d)$ where we can compute distances in two ways: via a ''strong'' oracle that returns exact distances $d(x,y)$, and a…