$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering
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 advers...