The computational complexity of some explainable clustering problems

DOI10.1016/J.IPL.2023.106437MaRDI QIDQ6121425zbMATH OpenFDO

Authors Eduardo S. Laber

Publication date 26 March 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.09643

zbMATH Keywords

clusteringcomputational complexitydecision treesexplainability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

Cites work

• Information Theoretical Clustering Is Hard to Approximate
• Interpretable clustering using unsupervised binary trees
• The hardness of approximation of Euclidean k-means

Cited in

(1)

• Impossibility of depth reduction in explainable clustering

This page was built for publication: The computational complexity of some explainable clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121425)