Oral Poster

Random Cuts are Optimal for Explainable k-Medians

Konstantin Makarychev · Liren Shan

Great Hall & Hall B1+B2 (level 1) #1725
[ ]
Thu 14 Dec 3 p.m. PST — 5 p.m. PST
 
Oral presentation: Oral 6D Theory
Thu 14 Dec 1:20 p.m. PST — 2:20 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.