Skip to yearly menu bar Skip to main content


Random Cuts are Optimal for Explainable k-Medians

Konstantin Makarychev · Liren Shan

Room R06-R09 (level 2)
[ ] [ Visit Oral 6D Theory ]
Thu 14 Dec 1:35 p.m. — 1:50 p.m. PST

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).

Chat is not available.