# Near-optimal Algorithms for Explainable k-Medians and k-Means

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 2 Jul 2021.

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

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [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)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Balancing the Tradeoff Between Clustering Value and Interpretability](https://mlsanity.com/paper/1912.07820/) (2019)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Interpretable Clustering via Optimal Trees](https://mlsanity.com/paper/1812.00539/) (2018)
- [Terminal Embeddings](https://mlsanity.com/paper/1603.02321/) (2016)
- [Hardness of Approximation of Euclidean k-Median](https://mlsanity.com/paper/2011.04221/) (2020)

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

- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [XClusters: Explainability-first Clustering](https://mlsanity.com/paper/2209.10956/) (2022)
- [Towards Explainable Clustering: A Constrained Declarative based Approach](https://mlsanity.com/paper/2403.18101/) (2024)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Dynamic Algorithm for Explainable k-medians Clustering under lp Norm](https://mlsanity.com/paper/2512.01150/) (2025)
- [Explainable Clustering of Mixture Models](https://mlsanity.com/paper/2411.01576/) (2024)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)

## Abstract (arXiv)

We consider the problem of explainable k-medians and k-means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem, our goal is to find a threshold decision tree that partitions data into k clusters and minimizes the k-medians or k-means objective. The obtained clustering is easy to interpret because every decision node of a threshold tree splits data based on a single feature into two groups. We propose a new algorithm for this problem which is tilde O(log k) competitive with k-medians with ℓ1 norm and tilde O(k) competitive with k-means. This is an improvement over the previous guarantees of O(k) and O(k2) by Dasgupta et al (2020). We also provide a new algorithm which is O(log3/2 k) competitive for k-medians with ℓ2 norm. Our first algorithm is near-optimal: Dasgupta et al (2020) showed a lower bound of Omega(log k) for k-medians; in this work, we prove a lower bound of tildeOmega(k) for k-means. We also provide a lower bound of Omega(log k) for k-medians with ℓ2 norm.