Impossibility of depth reduction in explainable clustering

DOI10.1016/J.IC.2026.105430MaRDI QIDQ7262271zbMATH OpenFDO

Authors Chengyuan Deng, Surya Teja Gavva, C. S. Karthik, Parth B. Patel, Adarsh Srinivasan

Publication date 11 June 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105430

zbMATH Keywords

Euclidean metricexplainable clusteringk-centerk-meansk-medianshallow trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A fast approximation scheme for low-dimensional k-means
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Almost tight approximation algorithms for explainable clustering
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Clustering to minimize the maximum intercluster distance
• Cutting glass
• Definitions, methods, and applications in interpretable machine learning
• Explainable k -means: don’t be greedy, plant bigger trees!
• scientific article; zbMATH DE number 7788494 (Why is no real title available?)
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• Inapproximability of clustering in Lp metrics
• Johnson coverage hypothesis: inapproximability of k-means and k-median in _p-metrics
• Local search yields a PTAS for k-means in doubling metrics
• Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
• Near-optimal explainable k-means for all dimensions
• The computational complexity of some explainable clustering problems
• The price of explainability for clustering

This page was built for publication: Impossibility of depth reduction in explainable clustering

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