Random Cuts Are Optimal for Explainable K-Medians
Abstract
We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable $k$-medians in $\ell_1$. The problem of explainable $k$-medians was introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian in 2020. Several groups of authors independently proposed a simple polynomial-time randomized algorithm for the problem and showed that this algorithm is $O(\log k \log\log k)$ competitive. We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by $2\ln k+2$. This bound matches the $\Omega(\log k)$ lower bound by Dasgupta et al (2020).
Cite
Text
Makarychev and Shan. "Random Cuts Are Optimal for Explainable K-Medians." Neural Information Processing Systems, 2023.Markdown
[Makarychev and Shan. "Random Cuts Are Optimal for Explainable K-Medians." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/makarychev2023neurips-random/)BibTeX
@inproceedings{makarychev2023neurips-random,
title = {{Random Cuts Are Optimal for Explainable K-Medians}},
author = {Makarychev, Konstantin and Shan, Liren},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/makarychev2023neurips-random/}
}