  In this paper we consider two metric covering/clustering problems -
\textit{Minimum Cost Covering Problem} (MCC) and $k$-clustering. In the MCC
problem, we are given two point sets $X$ (clients) and $Y$ (servers), and a
metric on $X \cup Y$. We would like to cover the clients by balls centered at
the servers. The objective function to minimize is the sum of the $\alpha$-th
power of the radii of the balls. Here $\alpha \geq 1$ is a parameter of the
problem (but not of a problem instance). MCC is closely related to the
$k$-clustering problem. The main difference between $k$-clustering and MCC is
that in $k$-clustering one needs to select $k$ balls to cover the clients.
  For any $\eps > 0$, we describe quasi-polynomial time $(1 + \eps)$
approximation algorithms for both of the problems. However, in case of
$k$-clustering the algorithm uses $(1 + \eps)k$ balls. Prior to our work, a
$3^{\alpha}$ and a ${c}^{\alpha}$ approximation were achieved by
polynomial-time algorithms for MCC and $k$-clustering, respectively, where $c >
1$ is an absolute constant. These two problems are thus interesting examples of
metric covering/clustering problems that admit $(1 + \eps)$-approximation
(using $(1+\eps)k$ balls in case of $k$-clustering), if one is willing to
settle for quasi-polynomial time. In contrast, for the variant of MCC where
$\alpha$ is part of the input, we show under standard assumptions that no
polynomial time algorithm can achieve an approximation factor better than
$O(\log |X|)$ for $\alpha \geq \log |X|$.
