  Given a metric space $(V, d)$ along with an integer $k$, the $k$-Median
problem asks to open $k$ centers $C \subseteq V$ to minimize $\sum_{v \in V}
d(v, C)$, where $d(v, C) := \min_{c \in C} d(v, c)$. While the best-known
approximation ratio of $2.613$ holds for the more general supplier version
where an additional set $F \subseteq V$ is given with the restriction $C
\subseteq F$, the best known hardness for these two versions are $1+1/e \approx
1.36$ and $1+2/e \approx 1.73$ respectively, using the same reduction from Max
$k$-Coverage. We prove the following two results separating them.
  First, we show a $1.546$-parameterized approximation algorithm that runs in
time $f(k) n^{O(1)}$. Since $1+2/e$ is proved to be the optimal approximation
ratio for the supplier version in the parameterized setting, this result
separates the original $k$-Median from the supplier version.
  Next, we prove a $1.416$-hardness for polynomial-time algorithms assuming the
Unique Games Conjecture. This is achieved via a new fine-grained hardness of
Max-$k$-Coverage for small set sizes.
  Our upper bound and lower bound are derived from almost the same expression,
with the only difference coming from the well-known separation between the
powers of LP and SDP on (hypergraph) vertex cover.
