# Dynamic Algorithm for Explainable k-medians Clustering under lp Norm

arXiv: https://arxiv.org/abs/2512.01150 · HTML: https://mlsanity.com/paper/2512.01150/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 1 Dec 2025.

## Builds on (most cited first, 11 of 11)

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Random Cuts are Optimal for Explainable k-Medians](https://mlsanity.com/paper/2304.09113/) (2023)
- [Fully Dynamic k-Clustering with Fast Update Time and Small Recourse](https://mlsanity.com/paper/2408.01325/) (2024)
- [Fully Dynamic k-Median with Near-Optimal Update Time and Recourse](https://mlsanity.com/paper/2411.03121/) (2024)
- [Approximation Algorithms for Clustering with Dynamic Points](https://mlsanity.com/paper/2006.14403/) (2020)

## Built on by (most cited first, 1 of 1)

- [Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale](https://mlsanity.com/paper/2603.22363/) (2026)

## Abstract (arXiv)

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 decision tree that partitions data into k clusters while minimizing the k-medians objective. These trees are interpretable because each internal node makes a simple decision by thresholding a single feature, allowing users to trace and understand how each point is assigned to a cluster. We present the first algorithm for explainable k-medians under lp norm for every finite p >= 1. Our algorithm achieves an O(p(log k)^{1 + 1/p - 1/p^2}) approximation to the optimal k-medians cost for any p >= 1. Previously, algorithms were known only for p = 1 and p = 2. For p = 2, our algorithm improves upon the existing bound of O(log^{3/2}k), and for p = 1, it matches the tight bound of log k + O(1) up to a multiplicative O(log log k) factor. We show how to implement our algorithm in a dynamic setting. The dynamic algorithm maintains an explainable clustering under a sequence of insertions and deletions, with amortized update time O(d log^3 k) and O(log k) recourse, making it suitable for large-scale and evolving datasets.