# Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 5 Jul 2021.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Metric dimension reduction: A snapshot of the Ribe program](https://mlsanity.com/paper/1809.02376/) (2018)
- [A light metric spanner](https://mlsanity.com/paper/1505.03681/) (2015)
- [A PTAS for the Steiner Forest Problem in Doubling Metrics](https://mlsanity.com/paper/1608.06325/) (2016)

## Built on by (most cited first, 6 of 6)

- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [A Bi-metric Framework for Fast Similarity Search](https://mlsanity.com/paper/2406.02891/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Approximation and generalization properties of the random projection classification method](https://mlsanity.com/paper/2108.06339/) (2021)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)

## Abstract (arXiv)

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset X onto a random d = O(dX)-dimensional subspace (where dX is the doubling dimension of X), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension d having an extra log log n term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of k-means and k-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of X.