Information Theoretical Clustering Is Hard to Approximate

DOI10.1109/TIT.2020.3031629zbMath1473.94024arXiv1812.07075OpenAlexW3114784257MaRDI QIDQ5151733

Ferdinando Cicalese, Eduardo Sany Laber

Publication date: 22 February 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.07075

zbMATH Keywords

clusteringapproximation and inapproximability resultsminimizing of entropy impurity

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15) Approximation algorithms (68W25)

Related Items

The computational complexity of some explainable clustering problems