Oral Poster
Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev · Liren Shan
Great Hall & Hall B1+B2 (level 1) #1725
[
Abstract
]
Oral
presentation:
Oral 6D Theory
Thu 14 Dec 1:20 p.m. PST — 2:20 p.m. PST
Thu 14 Dec 3 p.m. PST
— 5 p.m. PST
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.