Hierarchical Clustering via Spreading Metrics
  We study the cost function for hierarchical clusterings introduced by
[arXiv:1510.05043] where hierarchies are treated as first-class objects rather
than deriving their cost from projections into flat clusters. It was also shown
in [arXiv:1510.05043] that a top-down algorithm returns a hierarchical
clustering of cost at most $O\left(\alpha_n \log n\right)$ times the cost of
the optimal hierarchical clustering, where $\alpha_n$ is the approximation
ratio of the Sparsest Cut subroutine used. Thus using the best known
approximation algorithm for Sparsest Cut due to Arora-Rao-Vazirani, the top
down algorithm returns a hierarchical clustering of cost at most
$O\left(\log^{3/2} n\right)$ times the cost of the optimal solution. We improve
this by giving an $O(\log{n})$-approximation algorithm for this problem. Our
main technical ingredients are a combinatorial characterization of ultrametrics
induced by this cost function, deriving an Integer Linear Programming (ILP)
formulation for this family of ultrametrics, and showing how to iteratively
round an LP relaxation of this formulation by using the idea of \emph{sphere
growing} which has been extensively used in the context of graph partitioning.
We also prove that our algorithm returns an $O(\log{n})$-approximate
hierarchical clustering for a generalization of this cost function also studied
in [arXiv:1510.05043]. Experiments show that the hierarchies found by using the
ILP formulation as well as our rounding algorithm often have better projections
into flat clusters than the standard linkage based algorithms. We also give
constant factor inapproximability results for this problem.
