The computational complexity of some explainable clustering problems
Not on the map. Why?
Abstract (arXiv)
We study the computational complexity of some explainable clustering problems in the framework proposed by [Dasgupta et al., ICML 2020], where explainability is achieved via axis-aligned decision trees. We consider the k-means, k-medians, k-centers and the spacing cost functions. We prove that the first three are hard to optimize while the latter can be optimized in polynomial time.
Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 13 of its 22 references that are in the map. First posted on arXiv 20 Aug 2022.
Builds on
13 of 22 references.
References · 13
- 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
- 2020Explainable k-Means and k-Medians Clusteringcited by 67
- 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
- 2015The Hardness of Approximation of Euclidean k-meanscited by 25
- 2021On the price of explainability for some clustering problemscited by 21
- 2021Nearly-Tight and Oblivious Algorithms for Explainable Clusteringcited by 17
- 2021How to Find a Good Explanation for Clustering?cited by 16
- 2021Shallow decision trees for explainable k-means clusteringcited by 15
- 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
- 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
- 2021Almost Tight Approximation Algorithms for Explainable Clusteringcited by 12
- 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
1 more
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 2; 2026: 1.
4 papers.