Almost Tight Approximation Algorithms for Explainable Clustering

Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al.~citedasgupta2020explainable. Specifically, we focus on the k-means and k-medians problems and provide nearly tight upper and lower bounds. First, we provide an O(log k log log k)-approximation algorithm for explainable k-medians, improving on the best known algorithm of O(k)~citedasgupta2020explainable and nearly matching the known Omega(log k) lower bound~citedasgupta2020explainable. In addition, in low-dimensional spaces d ll log k, we show that our algorithm also provides an O(d log2 d)-approximate solution for explainable k-medians. This improves over the best known bound of O(d log k) for low dimensions~citelaber2021explainable, and is a constant for constant dimensional spaces. To complement this, we show a nearly matching Omega(d) lower bound. Next, we study the k-means problem in this context and provide an O(k log k)-approximation algorithm for explainable k-means, improving over the O(k2) bound of Dasgupta et al. and the O(d k log k) bound of citelaber2021explainable. To complement this we provide an almost tight Omega(k) lower bound, improving over the Omega(log k) lower bound of Dasgupta et al. Given an approximate solution to the classic k-means and k-medians, our algorithm for k-medians runs in time O(kd log2 k ) and our algorithm for k-means runs in time O(k2 d).