Priority-Aware Explainable Clustering

Explainable clustering aims to represent a given clustering using an interpretable model, such as a decision tree, while approximately preserving the original assignment cost. For $k$-medians clustering under the ${\ell }_1$ norm, prior work has shown that threshold decision trees achieve a competitive ratio of $\Theta (\log k)$, and that this bound is tight. In this paper, we introduce priority-aware clustering, a refinement of explainable clustering in which different centers have different priorities. We start with the setting in which all centers are split into two groups: a small number $m$ of high-priority centers and $k-m$ remaining centers. Our randomized algorithm outputs a threshold decision tree with $2k$ leaves that yields an improved competitive ratio of $O(\log m)$ for high-priority centers, while preserving an $O(\log k)$ guarantee overall. We further extend our results to settings with multiple priority classes or in which every center has its own priority. In the latter case, the competitive ratio for a center ranked $i$ is $\tilde{O}(\log i)$. Our results provide a more flexible framework for explainable clustering, enabling interpretable models that offer stronger fidelity guarantees for high-priority clusters while maintaining worst-case guarantees.