# Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

arXiv: https://arxiv.org/abs/2607.13217 · HTML: https://mlsanity.com/paper/2607.13217/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 14 Jul 2026.

## Builds on (most cited first, 10 of 10)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection](https://mlsanity.com/paper/1912.06983/) (2019)
- [Hierarchical Clustering: a 0.585 Revenue Approximation](https://mlsanity.com/paper/2006.01933/) (2020)
- [Approximation Strategies for Generalized Binary Search in Weighted Trees](https://mlsanity.com/paper/1702.08207/) (2017)
- [Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median](https://mlsanity.com/paper/2207.05150/) (2022)
- [Precedence-Constrained Decision Trees and Coverings](https://mlsanity.com/paper/2602.21312/) (2026)

## Abstract (arXiv)

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class F. We call this problem Hierarchical F-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of F: trees and graphs of bounded diameter. We present the first polynomial time O(log n·loglog n) and O(log n)-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes F for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call pF-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.