The computational complexity of some explainable clustering problems

08/20/2022

∙

by   Eduardo Sany Laber, et al.

∙

0

∙

share

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.