Fair Polylog-Approximate Low-Cost Hierarchical Clustering
Marina Knittel Max Springer John Dickerson MohammadTaghi Hajiaghayi
Research in fair machine learning, and particularly clustering, has been
crucial in recent years given the many ethical controversies that modern
intelligent systems have posed. Ahmadian et al. [2020] established the study of
fairness in \textit{hierarchical} clustering, a stronger, more structured
variant of its well-known flat counterpart, though their proposed algorithm
that optimizes for Dasgupta's [2016] famous cost function was highly
theoretical. Knittel et al. [2023] then proposed the first practical fair
approximation for cost, however they were unable to break the
polynomial-approximate barrier they posed as a hurdle of interest. We break
this barrier, proposing the first truly polylogarithmic-approximate low-cost
fair hierarchical clustering, thus greatly bridging the gap between the best
fair and vanilla hierarchical clustering approximations.