Skip to yearly menu bar Skip to main content


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 k-medians in 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(logkloglogk) competitive. We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by 2lnk+2. This bound matches the Ω(logk) lower bound by Dasgupta et al (2020).

Chat is not available.