# The Price of Explainability for Clustering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2023.

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

- [A Framework for Data-Driven Explainability in Mathematical Optimization](https://mlsanity.com/paper/2308.08309/) (2023)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale](https://mlsanity.com/paper/2603.22363/) (2026)
- [Explainable Clustering of Mixture Models](https://mlsanity.com/paper/2411.01576/) (2024)
- [A Goemans-Williamson type algorithm for identifying subcohorts in clinical trials](https://mlsanity.com/paper/2506.10879/) (2025)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)

## Abstract (arXiv)

Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings. We show that the price of explainability for k-medians is at most 1+Hk-1; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explanability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explanability (using any algorithm) is at least (1-o(1)) ln k, showing that our result is best possible, up to lower-order terms. We also improve the price of explanability for the k-means problem to O(k ln ln k) from the previous O(k ln k), considerably closing the gap to the lower bounds of Omega(k). Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable k-medians and k-means cannot be approximated better than O(ln k), under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means than its price of explainability.