Nearly tight bounds on the price of explainability for the \(k\)-center and the maximum-spacing clustering problems (Q2686110)

The article discusses the price of explainability for a clustering task, which refers to the unavoidable loss in terms of the objective function if the final partition is forced to be explainable. The authors investigate this price for the \(k\)-centers and maximum-spacing clustering problems, providing nearly tight bounds for a natural model where explainability is achieved via decision trees. The work is inspired by the recent research of Dasgupta et al. and expands on their work by presenting nearly tight bounds for two other goals that arise in relevant clustering problems. The authors note that most work in the field of explainable machine learning has been focusing on supervised learning, but there has recently been some effort to devise explainable methods for unsupervised learning tasks, particularly clustering. The article provides a detailed background on the topic and a comprehensive review of related work. The writing is clear and well-structured, making it easy to follow the authors' thought process. The authors also provide numerous references to previous work in the field, highlighting the significance of their contribution. The article is well-suited for researchers and practitioners interested in explainable clustering and provides useful theoretical insights into the price of explainability for different clustering problems. However, the technical nature of the article may make it less accessible to non-experts in the field. The authors' findings provide valuable insights into the tradeoff between explainability and the quality of the objective function in clustering problems, making the article a worthwhile read for those interested in the topic.