  Hierarchical Clustering is an unsupervised data analysis method which has
been widely used for decades. Despite its popularity, it had an underdeveloped
analytical foundation and to address this, Dasgupta recently introduced an
optimization viewpoint of hierarchical clustering with pairwise similarity
information that spurred a line of work shedding light on old algorithms (e.g.,
Average-Linkage), but also designing new algorithms. Here, for the maximization
dual of Dasgupta's objective (introduced by Moseley-Wang), we present
polynomial-time .4246 approximation algorithms that use Max-Uncut Bisection as
a subroutine. The previous best worst-case approximation factor in polynomial
time was .336, improving only slightly over Average-Linkage which achieves 1/3.
Finally, we complement our positive results by providing APX-hardness (even for
0-1 similarities), under the Small Set Expansion hypothesis.
