Greedy k-Center from Noisy Distance Samples

Neharika Jali, Nikhil Karamchandani, Sharayu Moharir

We study a variant of the canonical k-center problem over a set of vertices in a metric space, where the underlying distances are apriori unknown. Instead, we can query an oracle w…