We present the first algorithm for explainable $k$-medians under $\ell_p$ norm for every finite $p \geq 1$ and show how to implement our algorithm in a dynamic setting.

We develop a new approach to explainable clustering as defined by Moshkovitz et al. (2020) based on spectral graph theory