Dynamic Algorithm for Explainable k-medians Clustering under lp Norm

Konstantin Makarychev, Ilias Papanikolaou, Liren Shan

We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold dec…