D. Dereniowski

Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

The framework applies whenever the corresponding flat clustering problem, which is called Hierarchical Clustering, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees, and it is shown that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.