The computational complexity of some explainable clustering problems

2022/08/20 by Eduardo Sany Laber, Laber, Eduardo Sany · 2 citations
Computer Science · Mathematics · #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Rough Sets and Fuzzy Logic #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2208.09643

openalex publication_date 2022/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• SpEx: A Spectral Approach to Explainable Clustering
• Additive Models Explained: A Computational Complexity Approach

Related

• On the price of explainability for some clustering problems
• Impossibility of Depth Reduction in Explainable Clustering
• Near-Optimal Explainable k-Means for All Dimensions
• The Price of Explainability for Clustering
• Explainable Clustering Beyond Worst-Case Guarantees