  The Euclidean $k$-center problem is a classical problem that has been
extensively studied in computer science. Given a set $\mathcal{G}$ of $n$
points in Euclidean space, the problem is to determine a set $\mathcal{C}$ of
$k$ centers (not necessarily part of $\mathcal{G}$) such that the maximum
distance between a point in $\mathcal{G}$ and its nearest neighbor in
$\mathcal{C}$ is minimized. In this paper we study the corresponding
$(k,\ell)$-center problem for polygonal curves under the Fr\'echet distance,
that is, given a set $\mathcal{G}$ of $n$ polygonal curves in $\mathbb{R}^d$,
each of complexity $m$, determine a set $\mathcal{C}$ of $k$ polygonal curves
in $\mathbb{R}^d$, each of complexity $\ell$, such that the maximum Fr\'echet
distance of a curve in $\mathcal{G}$ to its closest curve in $\mathcal{C}$ is
minimized. In this paper, we substantially extend and improve the known
approximation bounds for curves in dimension $2$ and higher. We show that, if
$\ell$ is part of the input, then there is no polynomial-time approximation
scheme unless $\mathsf{P}=\mathsf{NP}$. Our constructions yield different
bounds for one and two-dimensional curves and the discrete and continuous
Fr\'echet distance. In the case of the discrete Fr\'echet distance on
two-dimensional curves, we show hardness of approximation within a factor close
to $2.598$. This result also holds when $k=1$, and the $\mathsf{NP}$-hardness
extends to the case that $\ell=\infty$, i.e., for the problem of computing the
minimum-enclosing ball under the Fr\'echet distance. Finally, we observe that a
careful adaptation of Gonzalez' algorithm in combination with a curve
simplification yields a $3$-approximation in any dimension, provided that an
optimal simplification can be computed exactly. We conclude that our
approximation bounds are close to being tight.
