  We present a novel approximation algorithm for $k$-median that achieves an
approximation guarantee of
  $1+\sqrt{3}+\epsilon$, improving upon the decade-old ratio of $3+\epsilon$.
Our approach is based on two components, each of which, we believe, is of
independent interest.
  First, we show that in order to give an $\alpha$-approximation algorithm for
$k$-median, it is sufficient to give a \emph{pseudo-approximation algorithm}
that finds an $\alpha$-approximate solution by opening $k+O(1)$ facilities.
This is a rather surprising result as there exist instances for which opening
$k+1$ facilities may lead to a significant smaller cost than if only $k$
facilities were opened.
  Second, we give such a pseudo-approximation algorithm with $\alpha=
1+\sqrt{3}+\epsilon$. Prior to our work, it was not even known whether opening
$k + o(k)$ facilities would help improve the approximation ratio.
