  In this paper we initiate a systematic study of exact algorithms for
well-known clustering problems, namely $k$-Median and $k$-Means. In $k$-Median,
the input consists of a set $X$ of $n$ points belonging to a metric space, and
the task is to select a subset $C \subseteq X$ of $k$ points as centers, such
that the sum of the distances of every point to its nearest center is
minimized. In $k$-Means, the objective is to minimize the sum of squares of the
distances instead. It is easy to design an algorithm running in time
$\max_{k\leq n} {n \choose k} n^{O(1)} = O^*(2^n)$ ($O^*(\cdot)$ notation hides
polynomial factors in $n$). We design first non-trivial exact algorithms for
these problems. In particular, we obtain an $O^*((1.89)^n)$ time exact
algorithm for $k$-Median that works for any value of $k$. Our algorithm is
quite general in that it does not use any properties of the underlying (metric)
space -- it does not even require the distances to satisfy the triangle
inequality. In particular, the same algorithm also works for $k$-Means. We
complement this result by showing that the running time of our algorithm is
asymptotically optimal, up to the base of the exponent. That is, unless ETH
fails, there is no algorithm for these problems running in time $2^{o(n)} \cdot
n^{O(1)}$.
  Finally, we consider the "supplier" versions of these clustering problems,
where, in addition to the set $X$ we are additionally given a set of $m$
candidate centers $F$, and objective is to find a subset of $k$ centers from
$F$. The goal is still to minimize the $k$-Median/$k$-Means/$k$-Center
objective. For these versions we give a $O(2^n (mn)^{O(1)})$ time algorithms
using subset convolution. We complement this result by showing that, under the
Set Cover Conjecture, the supplier versions of these problems do not admit an
exact algorithm running in time $2^{(1-\epsilon) n} (mn)^{O(1)}$.
