Random Cuts are Optimal for Explainable k-Medians

Konstantin Makarychev, Liren Shan

We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable k-medians in l1. The problem of explainable k-medians was introduced by Dasgupta,…