Tight Lower Bounds for Approximate & Exact $k$-Center in ${\mathbb{R}}^d$

Rajesh Chitnis, Nitin Saurabh

In the discrete $k$-center problem, we are given a metric space $(P,\text{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq P$ of $k$ centers which minimizes the…