Analysis of Ward's Method
  We study Ward's method for the hierarchical $k$-means problem. This popular
greedy heuristic is based on the \emph{complete linkage} paradigm: Starting
with all data points as singleton clusters, it successively merges two clusters
to form a clustering with one cluster less. The pair of clusters is chosen to
(locally) minimize the $k$-means cost of the clustering in the next step.
  Complete linkage algorithms are very popular for hierarchical clustering
problems, yet their theoretical properties have been studied relatively little.
For the Euclidean $k$-center problem, Ackermann et al. show that the
$k$-clustering in the hierarchy computed by complete linkage has a worst-case
approximation ratio of $\Theta(\log k)$. If the data lies in $\mathbb{R}^d$ for
constant dimension $d$, the guarantee improves to $\mathcal{O}(1)$, but the
$\mathcal{O}$-notation hides a linear dependence on $d$. Complete linkage for
$k$-median or $k$-means has not been analyzed so far.
  In this paper, we show that Ward's method computes a $2$-approximation with
respect to the $k$-means objective function if the optimal $k$-clustering is
well separated. If additionally the optimal clustering also satisfies a balance
condition, then Ward's method fully recovers the optimum solution. These
results hold in arbitrary dimension. We accompany our positive results with a
lower bound of $\Omega((3/2)^d)$ for data sets in $\mathbb{R}^d$ that holds if
no separation is guaranteed, and with lower bounds when the guaranteed
separation is not sufficiently strong. Finally, we show that Ward produces an
$\mathcal{O}(1)$-approximative clustering for one-dimensional data sets.
