Random Cuts are Optimal for Explainable k-Medians Konstantin Makarychev Northwestern University Liren Shan