mlsanityData to 7 Oct 2026

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

arXiv 2107.00798 ↗First posted 2 Jul 2021cs.DS cs.LGcited by 13

Not on the map. Why?

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.

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

Builds on

16 of 29 references.

References · 16

  1. 2020Explainable k-Means and k-Medians Clusteringcited by 67
  2. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  3. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  4. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  5. 2020ExKMC: Expanding Explainable k-Means Clusteringcited by 31
  6. 2014An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimizationcited by 26
  7. 2015The Hardness of Approximation of Euclidean k-meanscited by 25
  8. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  9. 2021On the price of explainability for some clustering problemscited by 21
  10. 2021Nearly-Tight and Oblivious Algorithms for Explainable Clusteringcited by 17
  11. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  12. 2021Almost Tight Approximation Algorithms for Explainable Clusteringcited by 12
4 more
  1. 2019Balancing the Tradeoff Between Clustering Value and Interpretabilitycited by 11
  2. 2018Interpretable Clustering via Optimal Treescited by 10
  3. 2016Terminal Embeddingscited by 5
  4. 2020Hardness of Approximation of Euclidean k-Mediancited by 5

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 2; 2023: 2; 2024: 4; 2025: 2.

13 papers.

Sort:

  1. 2021How to Find a Good Explanation for Clustering?cited by 16
  2. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
  3. 2021Shallow decision trees for explainable k-means clusteringcited by 15
  4. 2024Interpretable Clustering: A Surveycited by 8
  5. 2022The computational complexity of some explainable clustering problemscited by 4
  6. 2022XClusters: Explainability-first Clusteringcited by 2
  7. 2024Towards Explainable Clustering: A Constrained Declarative based Approachcited by 2
  8. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  9. 2023The Computational Complexity of Concise Hypersphere Classificationcited by 1
  10. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  11. 2024Explainable Clustering of Mixture Modelscited by 0
  12. 2025SpEx: A Spectral Approach to Explainable Clusteringcited by 0
1 more
  1. 2025Dynamic Algorithm for Explainable k-medians Clustering under lp Normcited by 0