{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T21:07:29Z","timestamp":1774040849274,"version":"3.50.1"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:00:00Z","timestamp":1772496000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2313372"],"award-info":[{"award-number":["CCF-2313372"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["825876"],"award-info":[{"award-number":["825876"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1016\/j.ic.2026.105430","type":"journal-article","created":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T00:17:38Z","timestamp":1772583458000},"page":"105430","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Impossibility of depth reduction in explainable clustering"],"prefix":"10.1016","volume":"310","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2586-3430","authenticated-orcid":false,"given":"Chengyuan","family":"Deng","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0845-5029","authenticated-orcid":false,"given":"Surya","family":"Teja Gavva","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"family":"Karthik C\u2024\u202fS\u2024","sequence":"additional","affiliation":[]},{"given":"Parth","family":"Patel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0288-4818","authenticated-orcid":false,"given":"Adarsh","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2026.105430_bib0001","series-title":"Approximation Algorithms","author":"Vazirani","year":"2001"},{"key":"10.1016\/j.ic.2026.105430_bib0002","series-title":"Interpretable Machine Learning","author":"Molnar","year":"2020"},{"issue":"44","key":"10.1016\/j.ic.2026.105430_bib0003","doi-asserted-by":"crossref","first-page":"22071","DOI":"10.1073\/pnas.1900654116","article-title":"Definitions, methods, and applications in interpretable machine learning","volume":"116","author":"Murdoch","year":"2019","journal-title":"Proc. Natl. Acad. Sci."},{"key":"10.1016\/j.ic.2026.105430_bib0004","series-title":"International Conference on Machine Learning","first-page":"7055","article-title":"Explainable k-means and k-medians clustering","author":"Dasgupta","year":"2020"},{"key":"10.1016\/j.ic.2026.105430_bib0005","series-title":"International Conference on Machine Learning","first-page":"5915","article-title":"On the price of explainability for some clustering problems","author":"Laber","year":"2021"},{"key":"10.1016\/j.ic.2026.105430_bib0006","first-page":"28929","article-title":"Nearly-tight and oblivious algorithms for explainable clustering","volume":"34","author":"Gamlath","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.ic.2026.105430_bib0007","series-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18\u201324 July 2021, Virtual Event","first-page":"7358","article-title":"Near-optimal algorithms for explainable k-Medians and k-means","volume":"139","author":"Makarychev","year":"2021"},{"key":"10.1016\/j.ic.2026.105430_bib0008","series-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"2641","article-title":"Almost tight approximation algorithms for explainable clustering","author":"Esfandiari","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0009","series-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"2580","article-title":"Near-optimal explainable k-means for all dimensions","author":"Charikar","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0010","doi-asserted-by":"crossref","first-page":"66890","DOI":"10.52202\/075280-2921","article-title":"Random cuts are optimal for explainable k-medians","volume":"36","author":"Makarychev","year":"2023","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.ic.2026.105430_bib0011","series-title":"64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6\u20139, 2023","first-page":"1131","article-title":"The price of explainability for clustering","author":"Gupta","year":"2023"},{"key":"10.1016\/j.ic.2026.105430_bib0012","article-title":"ExKMC: expanding explainable k-Means clustering","volume":"abs\/2006.02399","author":"Frost","year":"2020","journal-title":"CoRR"},{"key":"10.1016\/j.ic.2026.105430_bib0013","series-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","first-page":"1629","article-title":"Explainable k-means: don\u2019t be greedy, plant bigger trees!","author":"Makarychev","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0014","doi-asserted-by":"crossref","DOI":"10.1016\/j.ipl.2023.106437","article-title":"The computational complexity of some explainable clustering problems","volume":"184","author":"Laber","year":"2024","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.ic.2026.105430_bib0015","series-title":"Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","first-page":"400","article-title":"Optimal interpretable clustering using oblique decision trees","author":"Gabidolla","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0016","series-title":"International Conference on Machine Learning","first-page":"18652","article-title":"Cluster explanation via polyhedral descriptions","author":"Lawless","year":"2023"},{"key":"10.1016\/j.ic.2026.105430_bib0017","series-title":"Proceedings of the AAAI Conference on Artificial Intelligence","first-page":"3904","article-title":"How to find a good explanation for clustering?","volume":"36","author":"Bandyapadhyay","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0018","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.eswa.2016.06.009","article-title":"What makes classification trees comprehensible?","volume":"62","author":"Piltaver","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"10.1016\/j.ic.2026.105430_bib0019","doi-asserted-by":"crossref","DOI":"10.1016\/j.patcog.2022.109239","article-title":"Shallow decision trees for explainable k-means clustering","volume":"137","author":"Laber","year":"2023","journal-title":"Pattern Recognit."},{"key":"10.1016\/j.ic.2026.105430_bib0020","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","article-title":"Clustering to minimize the maximum intercluster distance","volume":"38","author":"Gonzalez","year":"1985","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.ic.2026.105430_bib0021","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/5925.5933","article-title":"A unified approach to approximation algorithms for bottleneck problems","volume":"33","author":"Hochbaum","year":"1986","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.ic.2026.105430_bib0022","doi-asserted-by":"crossref","DOI":"10.1137\/18M1171321","article-title":"Better guarantees for k-Means and Euclidean k-median by primal-dual algorithms","volume":"49","author":"Ahmadian","year":"2020","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ic.2026.105430_bib0023","series-title":"STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20\u201324, 2022","first-page":"1621","article-title":"Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets","author":"Cohen-Addad","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0024","series-title":"5th Online World Conference on Soft Computing in Industrial Applications (WSC5)","first-page":"4","article-title":"The curse of dimensionality","volume":"1","author":"K\u00f6ppen","year":"2000"},{"key":"10.1016\/j.ic.2026.105430_bib0025","series-title":"International Work-conference on Artificial Neural Networks","first-page":"758","article-title":"The curse of dimensionality in data mining and time series prediction","author":"Verleysen","year":"2005"},{"key":"10.1016\/j.ic.2026.105430_bib0026","series-title":"Applications of Dynamic Programming to Agricultural Decision Problems","first-page":"1","article-title":"Dynamic programming and the curses of dimensionality","author":"Taylor","year":"2019"},{"key":"10.1016\/j.ic.2026.105430_bib0027","series-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2\u20134, 1988, Chicago, Illinois, USA","first-page":"434","article-title":"Optimal algorithms for approximate clustering","author":"Feder","year":"1988"},{"key":"10.1016\/j.ic.2026.105430_bib0028","series-title":"2019 IEEE 60th Annual Symposium on Foundations of Computer Science","first-page":"519","article-title":"Inapproximability of clustering in Lp-metrics","author":"Cohen-Addad","year":"2019"},{"key":"10.1016\/j.ic.2026.105430_bib0029","series-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021","first-page":"2635","article-title":"On approximability of clustering problems without candidate centers","author":"Cohen-Addad","year":"2021"},{"key":"10.1016\/j.ic.2026.105430_bib0030","series-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022","first-page":"1493","article-title":"Johnson coverage hypothesis: inapproximability of k-means and k-median in Lp-metrics","author":"Cohen-Addad","year":"2022"},{"key":"10.1016\/j.ic.2026.105430_bib0031","series-title":"IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9\u201311 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA","first-page":"353","article-title":"Local search yields approximation schemes for k-Means and k-median in Euclidean and minor-free metrics","author":"Cohen-Addad","year":"2016"},{"key":"10.1016\/j.ic.2026.105430_bib0032","series-title":"IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9\u201311 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA","first-page":"365","article-title":"Local search yields a PTAS for k-Means in doubling metrics","author":"Friggstad","year":"2016"},{"issue":"3","key":"10.1016\/j.ic.2026.105430_bib0033","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1137\/S0097539702404055","article-title":"A nearly linear-time approximation scheme for the euclidean K-Median problem","volume":"37","author":"Kolliopoulos","year":"2007","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ic.2026.105430_bib0034","series-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018","first-page":"430","article-title":"A fast approximation scheme for low-dimensional k-means","author":"Cohen-Addad","year":"2018"},{"key":"10.1016\/j.ic.2026.105430_bib0035","article-title":"Near-linear time approximation schemes for clustering in doubling metrics","volume":"abs\/1812.08664","author":"Cohen-Addad","year":"2018","journal-title":"CoRR"},{"key":"10.1016\/j.ic.2026.105430_bib0036","series-title":"Proceedings of the Sixteenth Annual Symposium on Computational Geometry","first-page":"360","article-title":"Cutting glass","author":"Pach","year":"2000"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000283?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000283?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T19:19:58Z","timestamp":1774034398000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":36,"alternative-id":["S0890540126000283"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105430","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Impossibility of depth reduction in explainable clustering","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105430","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier Inc.","name":"copyright","label":"Copyright"}],"article-number":"105430"}}