Oral
Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev · Liren Shan
Room R06-R09 (level 2)
Abstract:
We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable -medians in . The problem of explainable -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 competitive. We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by . This bound matches the lower bound by Dasgupta et al (2020).
Chat is not available.