The computational complexity of some explainable clustering problems
This addresses the problem of understanding the theoretical limits of explainable clustering for researchers in machine learning and algorithms, but it is incremental as it builds on an existing framework.
The paper tackles the computational complexity of explainable clustering problems using axis-aligned decision trees, proving that optimizing k-means, k-medians, and k-centers is hard, while spacing cost can be optimized in polynomial time.
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.