Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm
Authors: Konstantin Makarychev
Ilias Papanikolaou
Liren Shan
Venue: NeurIPS 2025 spotlight ()
Keywords: Explainable Clustering
k-medians
Decision Tree
Primary area: theory
TL;DR: 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.

Abstract: 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 $\ell_p$ norm for every finite $p \geq 1$. Our algorithm achieves an $\tilde{O}\big(p(\log k)^{1 + 1/p - 1/p^2}\big)$ approximation to the optimal $k$-medians cost for any $p \geq 1$. Previously, algorithms were known only for $p = 1$ and $p = 2$. For $p = 2$, our algorithm improves upon the existing bound of $\tilde 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.

Dynamic Algorithm for Explainable k--medians Clustering under lp Norm
Konstantin Makarychey Northwestern
Ilias Papanikolaou" Northwestern
Liren Shan' TTIC
Abstract
We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). this problem, the goal is to construct threshold decision tree that partitions data into clusters while minimizing the k-medians objective. These trees are interpretable because each internal node makes simple decision by thresholding single feature, allowing users trace and understand how each point is assigned to cluster.
We present the first algorithm for explainable k-medians under lp norm for every finite p 2 1. Our algorithm achieves an (p(log k) k)1+1/p-1/p²) approximation the optimal k- medians cost for any 2 1. Previously, algorithms were known only for and p 2. For p 2, algorithm improves upon the existing bound Ölogg 3/2 k). and for p 1, it matches the tight bound of log k O(1) up a multiplicative (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 Old log k) and Ollog k) recourse, making it suitable for large-scale and evolving datasets.
Introduction
Artificial intelligence systems play an increasingly important role everyday life, influencing decisions that affect individuals, businesses, and society whole. As their impact grows, so does the need for transparency and human oversight. response, there a growing emphasis on making Al decisions understandable to people. This has led to the development of models that aim to present their makinn processes clear and interpretable manner.
In this paper, we study algorithms for explainable clustering. The notion of explainable k-means and k-medians clustering was introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020) as way to make clustering decisions more accessible to humans. Both k-means and k-medians are classical clustering objectives widely used in practice. Here, focus on /--medians clustering under the tp norm. A k-medians clustering of dataset X Rd is defined by collection of k centers c², e2,c...., c Each point E X is assigned to the closest center in the f, norm, that is, the center minimizing | e²I|p- Consequently, every clustering corresponds to a Voronoi partition under the lp norm. The cost of the clustering is defined
costp(X:oo
Σ
Σ
||
1lpp
#=1 xE
where P. denotes the set of points assigned to center clustering.
cf. We refer to this as unconstrained k-medians
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While this objective is simple to define and machines can easily compute the nearest centers, the resulting cluster assignments are often difficult for humans to interpret. To make clustering more comprehensible to humans, Dasgupta et al. (2020) proposed using threshold decision trees to represent clusterings. They referred to this approach as explainable k-means and k-medians. For k-medians, they considered the L norm. In a threshold decision tree, each internal node compares a single coordinate of the input to a threshold and directs the point to the left or right subtree accordingly. Each leaf of the tree represents a cluster. We denote the center assigned to x by the decision tree as Txx). The cost of the clustering is then defined similarly to the unconstrained case:
cost Most,((X7)) (X, = Σ x T(x)ll zEX
Assigning a data point to a cluster using a threshold decision tree avoids complex distance compu- tations and instead follows simple, transparent process: each decision is based on sequence of threshold comparisons. This makes it clear how a particular assignment was made and which features influenced it.
The central question how much clustering quality lost exchange for interpretability. This trade-off is captured by the the cost of explainability competitive ratio, defined as the worst-case ratio between the cost of the explainable clustering and that of the optimal unconstrained k-medians clustering:
cost (X, T) max X O
where OPTx,p(X) = mine, ex cost, (X; .I....,, ok) denotes the cost of the optimal (uncon- strained) k-medians clustering of X.
Dasgupta et al. (2020) showed perhaps surprisingly- that the competitive ratio for explainable k-medians under the & norm does not depend on the number of points in the dataset and can be bounded solely as a function of k; specifically, it is at most (A)). They also established lower bound of 2loog k). This result sparked significant interest and led to extensive study of explainable k-medians under the & norm. Makarychev and Shan (2021) and Esfandiari, Mirrokni, and Narayanan (2022) improved the upper bound to Ó(lg k)); see also Laber and Murtinho (2021) and Gamlath, Jia, Polak, and Svensson (2021) for related results. The approximation factor was later improved to (log k) by Gupta, Pittu, Svensson, and Yuan (2023) and Makarychev and Shan (2023). Finally, Gupta et al. (2023) established a tight upper bound of (1 + Hg-1) for the & norm, where Ha-1 denotes the (k- 1)st harmonic number. Bandyapadhyay. Fomin, Golovach, Lochet, Purohit, and Simonov (2022) developed fixed-parameter tractable algorithms that compute the optimal explainable k-medians clustering under the & norm in time (nd) (o))))+(1)) and n n²d(n)) They also proved that the problem is NP-complete and cannot be solved in (k)))())) time for any computable function f()) unless the Exponential Time Hypothesis (ETH) fails. Gupta al. (2023) showed that this problem is hard to approximate better than (1/2- o(1)) In k unless P=NP.
Beyond the é case, much less was known. For p > 1, the only prior result was due to Makarychev and Shan (2021), who provided O(log3/2 (ts////))cooppppe k))competitive algorithm and lower bound of M(log k) for the Eg norm. In this paper, we extend the study of explainable k-medians clustering to general Ep norms with finite p 1. Specifically, we design an algorithm that constructs threshold decision tree with & leaves, such that the cost of the resulting clustering satisfies
(X, S O(p log 111/p11/22 k: log log k) OPTx,p(X).
This improves upon the best known bound for = 2, and for = it matches the optimal guarantee up to an Olog log k) factor. Note that the exponent of the logarithm, 1 1/p 1/p², always lies in the interval [1, 1.25].
We now discuss the second contribution of the paper. In recent years, researchers have tumndd their attention to dynamic clustering algorithms, which maintain a high-quality clustering as the dataset evolves and is continuously updated. Recent work in this area includes papers by Lattanzi and Vassilvitskii (2017); Chan, Guerqin, and Sozio (2018); Cohen-Addad, Hjuler, Parotsidis, Saulpic, and Schwiegelshohn (2019); Deng, Li, and Rabani (2022); Bhattacharya, Costa, Lattanzi, and Parotsidis (2023); Bhattacharya, Costa, Garg, Lattanzi, and Parotsidis (2024); Bhattacharya, Costa, and Farokhnejad (2025).
2

---

Dynamic algorithms are typically evaluated based on two key metrics: the update time for insertions and deletions, and the recourse- the number of changes made to the solution (in this case, centers inserted or deleted) in response to each update. Bhattacharya et al. (2025) presented an approximation algorithm with ((1) >-apprxximation ratio, O(log² A) recourse and Olk) update time (where A is an aspect ratio of the metric space).
In this paper, we initiate the study of dynamic algorithms for explainable k-medians clustering. Specifically, ask whether our explainable algorithm can be combined with state-of-the-art dynamic k-medians clustering algorithms-aae we answer this question affirmatively.
Most known algorithms for explainable k-medians clustering first compute clustering using an existing fff-the-shelf method, which we refer to as the reference clustering, and then use it to construct decision tree. Importantly, this second step is oblivious to the dataset-tha that is, it relies only on the reference clustering and not on the actual data points. Our algorithm is no exception: it takes as input set of reference centers and outputs threshold decision tree whose cost is upper bounded by Ö(p log 111p-1/11"/ k) times the cost of the reference clustering. However, existing algorithms for explainable clustering not designed to operate in dynamic setting.
We present a dynamic implementation of our algorithm, which the set of reference centers evolves over time through insertions and deletions. Our algorithm supports updates in Oddlog" k)) time and modifies only O (log k) nodes in the tree per update (i.e., it has Ollog k) recourse). while maintaining the same Ö(p log 1+1/--1/1² k) competitive ratio.
Our algorithm can be integrated with the dynamic algorithms for unconstrained k-medians mentioned above. We begin by updating the set of centers using one of these low-recourse algorithms, and then apply our dynamic algorithm to update the decision tree for explainable clustering. Our algorithm can also be used to construct explainable clusterings for multiple values of k for example, when selecting a suitable k within a given range using the elbow method. In such cases, we can run an algorithm (such as k-means++) that outputs centers incrementally, and feed these centers into our dynamic algorithm, which updates the decision tree on the fly.
1.1 Techniques
Our static algorithm for explainable k-medians under the Ep norm builds on and refines a prior algorithm by Makarychev and Shan (2021) developed for the Eg norm. In this work, we generalize the approach to all Ep norms with finite 2 1 and provide a tighter analysis. In particular, for the & norm, we improve the competitive ratio from the previous bound of Ö(log" 1.5 k) to Ö(log' 1.25 k).
As noted earlier, our algorithm takes as input a set of reference centers produced by off- clustering algorithm and does not access the dataset points directly.
This algorithm relies on the PARTITION LEAF procedure. Each call to PARTITION LEAF takes cell of the space containing some subset of centers Cu and constructs partial threshold decision tree that partitions the cell into several subcells, each containing at most f fraction of the input centers, where 7 < 1. We apply PARTITION LEAF recursively, starting with the cell containing all centers Ci...., Ck. to construct the full decision tree.
PARTITION_LEE _LEF first selects an anchor point within the cell. This anchor, denoted m² is the median or an approximate median of the centers in C, and remains fixed throughout the execution of PARTITION LEAF. The procedure partitions the space using random cuts drawn from a specially crafted distribution. Each time cut is sampled and applied (some cuts may be discarded). the algorithm removes the centers that are separated from the anchor and places them into one of the output parts. Each cut is defined by a coordinate i and threshold 0, and has the form Le {ir x; < 0} and Right- = {x: x; 2 07. If a sampled cut does not separate any centers, it is discarded.
Random cuts in the algorithm are drawn as follows: PARTITION LEAF selects a random coordinate i E (1...., d). random threshold 0' E [0, R.), and random sign E (+1} (where R; is the radius of the cell; see Section 2 for details). It lets 0 = m. + a0'. The cumulative density function for 0' is given by xP/ R2. The algorithm terminates when fewer than on centers remain unseparated from the anchor.
3

---

We note that using a uniform distribution for 0 (i.e., selecting random coordinate i and then choosing a threshold 9 uniformly at random from R, R,]) would result in a poor competitive ratio, as illustrated in the following example. Consider a k-medians clustering with the lp norm, defined by +- 1 centers located at the positions c1,... Cd, and 0, where e, denotes the i-th standard basis vector. We focus on a single data point x with coordinates (c....,e) .)). Suppose we pick cuts by selecting a random coordinate+ i E {L....,d d} and a threshold 0 E [o, 1J uniformly at random. In this case, constant fraction of the centers will be separated from the anchor m" in @ak) steps. The probability that one of the cuts made during these steps separates x from its closest center (the center located at the origin) is ((Ek), assuming is sufficiently small. If x is separated from 0, it will be assigned to a different center, i.e., one of the vectors e₁. In that case, the l distance from x to the new center is approximately 1. Therefore, the expected cost of the clustering produced by this variant of the algorithm for point is @(Ek), while the optimal (unconstrained) cost is e/ Hence, the competitive ratio of such an algorithm is at least ((k2-1/p)
In this paper, we prove through careful analysis of the algorithm that the aforementioned choice of random distribution yields an (pp Opllog"' competitive ratio.
loggll 11/1p-/1// log log k) upper bound on the algorithm's
We then show how to implement our static clustering algorithm in the dynamic setting. Our approach builds the idea of assigning each decision node timestamp drawn from exponential distribution a technique previously introduced in Gupta et al. (2023); Makarychev and Shan (2023) solely for the purpose of analyzing an explainable clustering algorithm under the é norm. We extend this idea by integrating the exponential clock directly into the algorithm's 's design. Specifically, we assume that random cuts selected with arrival rates governed by a Poisson process. Each cut is assigned timestamp corresponding to its selection time.
The high-level idea behind the dynamic algorithm is follows. When new center is inserted, we identify the earliest cut - based on its timestamp - that separates the new center from the anchor. To efficiently find such cut, we employ data structures that enable this operation in O(d log k) time. We prove that this earliest cut corresponds to the one that would have been used by the static algorithm to separate the center from the anchor m.. There are two possible cases: either the decision tree already contains a node corresponding to this cut, or it does not. In the latter case, the algorithm creates a new decision node incorporate the cut.
Implementing this idea presents several challenges. The dynamic PARTITION LEAF algorithm not permitted to modify the anchor; consequently, it may need to rebuild the entire decision tree for cell and its descendants once the number of updates in that cell exceeds certain threshold. Moreover, the dynamic algorithm must terminate at a fixed time-one that cannot be adjusted as centers are added or removed. As a result, unlike the static version, it cannot stop based on the number of remaining centers falling below a given threshold. In this paper, address these challenges and present complete dynamic algorithm for the problem.
2 Algorithm
In this section, we present our algorithm for constructing an explainable clustering tree for the k-medians problem in Ep space. The algorithm takes set of k centers C' as input and produces a binary threshold tree T with & leaves, each leaf containing a distinct center in C. The construction begins by initializing the root node of the tree with all centers C, and recursively partitioning the centers using the procedure PARTITION_LEAS (as shown in Figure 1). We initiate the construction by calling CERITTIO___FA((1)
While this algorithm is static, we show an efficient dynamic algorithm that achieves the same behavior as this algorithm in Section 5. To couple the dynamic algorithm with the static algorithm, we present our algorithm based on two oracles: STOPPING_ORAAE ORACLE and GET_ANCHOR. The STOPPING ORACLE takes a cut w and the current subtree Ta rooted at u as input and outputs a Boolean value; if it is True, then stops partitioning centers; otherwise, the algorithm continues to partition centers. This oracle guarantees that when partitioning stops, every leaf in Tu contains at most a 7 fraction of centers in C... where 7 < 1. The oracle GET_ANCHOR takes a subset of centers C, and returns an anchor point m E Rd such that for each coordinate E [d]] at least 1/4 of centers in C,, lie on either side of my i.e. Iec E C. G 2 m 2 |C.l/4 and
He C. c. m H Z |Cul/4. /4. In the static version, we can simply choose the anchor m " as the

---

coordinate- wise median of Cu, and the STOPPING ORACLE returns True if and only if the main part contains fewer than 1/2 centers in C.,, i.c. |Cuol C2.1/2.
Algorithm PARTITION_LES
Input: a node u with set of centers Cy C I Output: threshold tree Tu
1. Set the anchor m = GET_ [EHE_ANCHOR(C.)
2. Set the main part = u and Cuo = C2 and step / = 0. Set the subtree T, to have only the root
3. We iteratively sample cuts wa until STOPPING ORACLE(W,, Tu) returns True:
(a) Update / L 1 and the radius R2 maxegC... ||c m lpp-
(b) Sample a threshold cut wi = (i,, 0.) as follows. Sample i, E f1, ... d}. ot E 1-1, 13. and (0,)a E [0, (R,)*) ) uniformly at random. Then, set 0, m., + a,0,-
(c) If the cut wa separates any centers in Cuo. then
Add two children up, ug the main part ug and split the centers into two parts Ca, = {c E Cu.
< 0z} and Cun = {c Cuo Cs, 2 11). Update the main part up = uy and Cuo = Cu. oz = 1; otherwise Ug u. and Cuo Cux (ug always contains m
4. Call OERTITIONLLAA(() for each leaf containing more than one center in the subtree rooted at u.
5. Return the tree Tu rooted at node u.
Figure 1: Algorithm PARTITION_ LEAF for explainable k-meddans in Ep
We now describe the procedure PARTITION LEAF(u). The procedure PARTITION LEAF(U) oper- ates on a node u that contains a set of centers C It first queries the oracle BET_ANCHOR to get an anchor point m. We always refer the leaf that contains " the main part, and denote it by uo- Initially, we set
u.
PARTITION LEAF iteratively splits the subset Cn using randomized threshold cuts until the STOPPING ORACLE returns True. In each iteration t, it computes the maximum Ep distance from m" any center in the current main part Cug- denoted by R, max.ec.,, ||c mmn 7/ Then, it samples random threshold cut 4a follows. coordinate E (1,2, 2, d) and sign a, {-1,1) are chosen uniformly at random. Next, it draws random variable 2, uniformly from the interval Jo, (R, )1 and set 6₂ = (Z.) l/P. The resulting threshold cut is W, = (fe. 12)). where 02 = m + o₂ Ot. If this threshold cut separates at least two centers in Cu., the algorithm partitions the current main part ug into two disjoint cells. adds two children ur un to the node uo and assigns centers Ouz = {c E CNp Ci < 0.) node ur. and centers Gug = {c E Cuo Cj 2 de) node wR- TTe child node, either uz or u.s that contains anchor m becomes the updated main part uo-- This process continues until the STOPPING ORACLE returns True. Finally, recursively calls the OORTITION_LEA(( on each leaf' v that contains more than one center in the subtree rooted at u.
3 Analysis of approximation factor
In this section, we provide the approximation guarantees for our algorithm.
Theorem 3.1. Given of points X and set of k centers C, for any p 1, Algorithm finds threshold tree T with leaves that has k-medians cost
Elcost (X, T) < 5 (p ()ogk) + + log log k) (ostp(X.C)
We analyze the approximation guarantee by bounding the expected cost incurred by each point x E X. Fix an arbitrary point z e X and let e C' be its closest center. We show that the expected cost of
5

---

assigning x in the constructed threshold tree T is bounded by
E|cost,(2, T) < O (p- (log (logk) k) - log log k) || cllp.
x equals its closest center c, then a is always assigned to by any tree T, and thus incurs zero cost, costpt p (z, T)= = 0. In this case, the above bound holds trivially. Therefore, we may assume from now on that x: o c.
Consider the path from the root to the leaf in the tree that contains this point We index the node on this path by = 1, 2, ... T. where in is the root of the tree and uy is the leaf that contains æ. Let Te be the partially built tree when the node Ue is generated in the algorithm. Given any tree Te, let (ax) be the closest center in the same leaf as x in tree Tt. We define the following upper bound on the approximation factor.
Definition 3.2. Let Aş be the smallest number such that the following inequality holds for every partially built tree Te,
E (x, T) T:. S Ax || -x)(x))
Since all centers are contained in the root u1, we have (x)) = c. Thus, we have A is an upper bound on the approximation factor. We then prove the following lemma, which provides recurrence relation for bounding Ak-
Lemma 3.3. For some absolute constant O, we have for any step
cost, (z, T) |
2Ap
+ 3 p(log k) * -log(AA log" k).
E
( Te- S
3
+
k
We first show how to use Lemma 3.3 to get the desired bound on As. which also provides the approximation factor for the algorithm.
Proof of Theorem 3.1. By Lemma 3.3 and the definition of As, we get the following recurrence E + p(log k) 2+ + (og(AA log" k:). Then, we have that A₃ is bounded by A < O p(log k) 1 log log k) By the definition of Ag. we bound the expected cost of any point X given by tree as shown in Equation (1). By taking the sum over all points in X, we get the approximation factor for the algorithm.
relation on Ak, A I 3 +
2
3.1 Radius and diameter bounds
Before proving the main recurrence lemma, establish several key results that describe how the radius and diameter of clusters evolve during the recursive partitioning process. These results serve as essential tools in our main proof. We defer the proofs to Appendix A.I.
We first show that the radius R., decreases exponentially in one partition leaf call. Consider any partition leaf call a node u. Let R, be the radius of the main part before the iteration of this partition leaf call. Then, we have R₁ = Rag We use Te to denote the partial tree given by the algorithm before the iteration i of this partition leaf call.
Lemma 3.4. Consider any partition leaf call on node we have Pr(Re+L. > R,/2 T.) S E
Let == 22p++,dInk k). Then for every 1 2 1,
We define the diameter of node be D, == maxe,e'EC ||c- We use the following relation between R, and D., for node u at the beginning of partition leaf call, which generalizes Lemma 6.1 in Makarychev and Shan (2022) to lp norm.
Lemma 3.5 (Lemma 6.1 in Makarychev and Shan (2022)). For every node which the algorithm calls partition leaf. we have R R//44// < D. < 2R...
We define D., for every node u as follows. If the algorithm calls partition leaf on node u, then D., = D,. Now consider any node v in the partition leaf call of a node u, on which the algorithm does not call the partition leaf. Let d(u, v) be the distance from v to a in the tree. We set ñ, =
max { Day D. R_1 By the definition, D., is an upper bound of the diameter D., for every node R.

---

u. We now show that D., is non non-increddd increasing along any path from the root to a leaf in the tree. Since R. is non-increasing in one partition leaf call, D, is also non-inereasing in one partition leaf call. Moreover, since D, 2 Dr for every node v and D, D.. on node u where the algorithm calls partition leaf, we have D, is also non-increasing across partition leaf calls.
Lemma 3.6. For every node we have Ru/4V/ - Du S 2R
We then show that Du decreases exponentially along any path from the root to leaf in the tree. Lemma 3.7. Let L' [ d'nn k.. For every node let node be any descendant of u at depth L' in the tree T. Then, we have Pr D. 2 D2/2 Ta) S R3
3.2 Recurrence lemma
In this section, we provide proof overview of Lemma 3.3, which establishes the recurrence relation of Ag- The details of the proof are deferred to Appendix A.2.
We fix an arbitrary point x E X. Without loss of generality, we consider the step t* = and then in C. We then focus on the nodes in T that contain this point æ, which form a path from the root to the leaf containing 2. We index the node along this path by step / 1,2, T, where i1 is the root of the tree and wr is the leaf that contains Let Tr be the partially built tree when the node is generated in the algorithm.
Te (x) e is the closest center
We now bound the cost of this point given by the tree T. We begin by assuming that the radius R2 and the diameter substitute Dj decrease by a factor of 2 after every L and L' steps, respectively. By Lemma 3,4 and 3.7, and applying the union bound over all iterations, this good event holds with probability at least 1/k. If this good event fails to hold, then we simply upper bound the expected cost of x by A& || - cllp- which contributes the Ag/k factor.
Consider node u, such that both and contained in ug, and let wi be the cut sampled at this node. Let C. be the set of centers contained in un and D, be the diameter of u4. If x and e are separated by this wi, then x is eventually assigned to different center in C2 by T. By the triangle inequality, we have the cost of x in T is at most || cllp + D,- Alternatively, we can use a more refined bound based on the notion of the fallback center, following the approach in Makarychev and Shan (2021, 2022). If x is separated from c by this cut wt. then we define the fallback center of x to be the closest center c' Ce4.1 depends on the tree T' and the cut w/e Let M, (wr) denote the distance fro m x to the fallback center. Then. by the definition of Ag. the expected cost of x can also be upper bounded by (,
that is not separated from x by this cut wt. This fallback center
We now partition the steps {1,2, ................................ .T} into three disjoint cases based on the radius Re and the fallback distance Me(w) as follows. We introduce the following definitions.
Definition 3.8. For fixed parameter o > O, we say that step is light step if the radius satisfies
R₂ S log" i max {1|= - m'Ilp ||c m ml1ppp]
Otherwise, step t is called heavy step.
If x and e are separated by a cut wi then we refer to this cut as a light cut if step f a light step, and heavy cut if step t is heavy step.
Definition 3.9. For each step f, we say cut we separating x and c a safe cut if Me S Otherwise, this cut we called an unsafe cut.
Re 6r log R
Therefore, if x and are separated by the tree T, then exactly one of the following three events must occur: (I) they are separated by a safe cut; (2) they are separated by light cut; (3) they are separated by a heavy and unsafe cut. We then show how to bound the contribution of each case to the expected cost separately.
Safe cut: Suppose and are contained in node u,. The probability that x and c are separated by the cut w, is at most
p|lz c|pp[11= m 1p 11p-1
||c mm me'1pp-1)
Pr(x & c separated by wi | T S
2d
R
7

---

In this case, we use Mr as the upper bound of the expected cost since it is much smaller than the radius R, We show that 3R, 2 || m' lpp + ||c m' Ilp. Thus, the expected cost of safe An 33 || - cllp. each partition leaf call, we know that M, is cut at step is at most 2d R. non-decreasing as increases and RG decreases by a factor of after every steps. Hence, A& / R forms an increasing geometric series every L steps. Since Ag / R, S (6 log" k) for safe cuts, the expected cost due to safe cuts in one partition leaf call is most
2
L.
3 cllp
| cllp-
2d 62 log' h
log
Combining over all (loo k) partition leaf calls, this case is bounded by ((1) || cllp-
Light cut: Consider the node un contains x and c. The probability that æ or c is separated from the anchor m² by Wi is at least
max - m²Il l|c m²1p))
Pr(x or separated from m' by we Tr) 2
2d
R
Thus, in each partition leaf call, the probability that and are separated by light cut the end of the partition leaf call is most
pla cllo - m 11 + ||c m 1
max ||0: m² m²1 11 m
We upper bound the expected penalty D; S 2R, 12 log" k max {||> m' m'llp. ||e m' m'llp) by the definition a light cut. Since the number partition leaf calls is at most O(log k), the expected cost due to light cut is at most
(log k) DD p|a cll m² [1 1 + ||e m m1
s Ooglog'' 1-a k))l - cllpp-
max || - m I ||e m² [PP]
contained in node uy. For each coordinate i, we define Ut( = {1) (i, () is unsafe} to be all thresholds & such that the cut wi (i, 9) is unsafe step f. Let (t) be the Lehesgue measure of the unsafe threshold Ut)... Then, the probability that x and c are separated by an unsafe cut at the heavy step is at most
Heavy and unsafe cut: Consider heavy step t when æ and
max
maxflen [r
mfl lc m 8t(t).
2d
R
1=1
Note that all steps in Ps in one partition leaf call uses the same anchor point m². Let P C P. be all heavy steps in the partition leaf call. We define a vector ((s) E IRd whose i-th coordinate is (s) Ee 8, (t). By summing the above separation probability over all steps in P and applying Hölder's inequality, the probability that x and e are separated by a heavy and unsafe cut partition leaf call is at most
|| - m
||c m 1g-
P 2d
-(1(()))lp
R
In this case, we upper bound the penalty of separation by D. I 2R, Since R. 2 6log max [|| - mm'lpp ||c m m'lpp? for heavy steps, we have the expected penalty due to heavy and unsafe cuts at most
s
p
2
Σ (l((s)l
d lo k)p-T
==1
We then bound E [|)()) Since the number of partition leaf calls = Olog k), we show that
s
S
Σ
[A(s) logg-:o
Σ (ss)
Consider any fixed cut (i, 9) that separates and This cut is unsafe at step if and only if Me(w) 2 Re/(6" log" k As). Moreover, it always holds Me(w) Dr. By Lemma 3.6,

---

have Rg 2 Dr and D 2 Dr. Since by Lemma 3.7, D, decreases by a factor of 2 after every L'= f I kl] steps, this cut w is unsafe in at most L' log((2 6" log" k AA) steps. Thus, we have
s
Σ
Ass)
- 0 doog k. plog(log* k A+))ll= cllp-
Therefore, the expected cost due to heavy and unsafe cuts is at most
(log k)² - -a(p-11) log(log" k An)) || cllp.
Finally, combining all three cases and taking = 1/p 1/8², we get the conclusion.
Lower bounds
In this section, we present two lower bound results for explainable k-medians under Ep norms. First, we provide an (log k) lower bound on the competitive ratio of explainable k-medians under ép norm, for any fixed p 2 Second, we show that no explainable clustering algorithm can, without knowing in advance, achieve a good competitive ratio simultaneously for all 2 1. In particular, there exists an instance on which any such algorithm incurs a competitive ratio ((d)/4) for some p 2 1.
We extend the lower bound instance for explainable k-medians in E2 by Makarychev and Shan (2021) to all Ep norms with p 1. The proof is provided in Appendix D.
Theorem 4.1. For every p 2 1, there exists an instance X C TRd, such that for every threshold tree T, its clustering cost is at least (X, T) 2ilogg k) x..pxpppP) where OPT (X)(a cost of the optimal (unconstrained) k-medians clustering of X.
(X) is the Ep
The competitive ratio of our algorithm is upper bounded by Opp(og k)1+1/o-1//" Thus, for every
p > there remains Ó(log k)) 1/p-///""" gap, which is maximized at p 01ogg//1B) k))
We then investigate whether it is possible to design an explainable clustering algorithm that, without knowing p in advance, produces a single threshold tree (or distribution over threshold trees) with good competitive ratio for all 2 simultaneously. The following theorem shows that this is not possible. The proof is in the Appendix C.
Theorem 4.2. There exists an instance X C Rdd such that for any distribution over threshold trees, the expected competitive ratio is at least (4))/4) for some p 2 1.
5 Dynamic algorithm
In this section, we present a dynamic algorithm for the setting where the input set of points and centers C' change over time. We show that after each update, our algorithm maintains threshold tree with low k-medians cost and analyze its update time and recourse.
Let X2, , be the corresponding sequence of center sets. Our goal is output after each update threshold tree To with [Crl leaves that approximates the clustering of X, with centers C.. Similarly to the static setting, our dynamic algorithm only depends on the center sets to construct the trees T,. Thus, we focus on the setting where the center sets change through a sequence of insertion or deletion requests, i.e. C. = Ct-1 U (c), if is an insertion request of new center c, or C. Ct-1 {c}. if is a deletion request of an existing center e E Ct-1- We show the following theorem, with the proof in Appendix B.
denote a changing data set after each update t and let C₁, Cz...., Bt....,C..... Ct....
Theorem 5.1. Given sequence of requests, where each request is either an insertion deletion of single center in Rd, there is a dynamic algorithm that for each center set Ct. outputs a threshold tree Tn such that for any data set X C Rdd.
E E(cost,,(X, (XX,T) TO) S O(p (log k1)1+1/p-11/2 log log kt) (X,
where hy = |Ct)- The amortized update time of the algorithm is Odd k) and the amortized recourse (number of tree nodes updated) is Ollog k), where k max Cc,).

---

Note that naively classifying a data point x using a threshold tree Ti takes ((k) time in the worst case, T has height Ok)). In contrast, our dynamic algorithm efficiently updates the current threshold tree in only Odd k) time, by modifying on average Olog k) nodes after each request.
Moreover, our dynamic algorithm extends naturally to the fully-dynamic explainable clustering setting, where the input is a stream of insertion or deletion requests of data points instead of centers. Specifically, we invoke a fully-dynamic clustering algorithm by Bhattacharya et al. (2025) to maintain sequence of center sets C, that provide constant-factor approximation
X,. Since the algorithm of Bhattacharya et al. (2025) guarantees that only Õ(1) centers change on average after each update. our dynamic algorithm applies directly by treating each center change as center update request and invoking Theorem 5. See Corollary B.6 for the formal statement.
To implement our dynamic algorithm, we reinterpret the PARTITION LEAF procedure (Figure 1) in equivalent but more convenient way using the exponential clock. This version generates all random cuts in advance. Without loss of generality. we assume that all centers lie within [-1, otherwise, we rescale the instance accordingly. The procedure generates infinite sequence of candidate cuts w1, w2,,... where each cut Wi = (iz, (0,) is constructed as follows: a coordinate i, a sign o, {- and parameter Ze E [0, 29] are sampled uniformly at random. The threshold is then set 02 = mi, + a. (Z,)²/P, where m denotes the anchor point. Additionally, each cut w, is assigned an arrival time Pt. such that P1 S P2 ... follows the arrival times of a Poisson Process with rate À 1.
The algorithm attempts the next cut (We, Pe) in the sequence until the STOPPING ORACLE returns True. If wt separates at least two centers from the main part, the cut is made; otherwise, it is ignored. Since the arrival times Pt are independent of cut choices wi, this version yields the same distribution of threshold trees as the original PARTITION_ LEAF procedure. These arrival times At are crucial for the design of our dynamic algorithm. In the following discussion, we assume there is a data structure that stores this sequence of cuts with their arrival times. It also provides function GET GET_EARIL SETT_EARRISSTT. CUT that takes a center and returns the earliest cut w from the sequence that separates c and the anchor m.
We provide dynamic implementation of the PARTITION_LEAM procedure, which we apply recur- sively to obtain a fully dynamic version of the entire clustering algorithm. The dynamic variant of PARTITION LEAF supports three operations: (1) REBUILD, (2) INSERT CENTER, and (3) DELETE CENTER. We now briefly describe each of these operations.
Reconstruct the subtree rooted at node u, partitioning all centers in C. into distinct leaves via recursive calls to the PARTITION_ LEAF procedure. particular, GET AA.HHOCCCO) returns the true coordinate-win wise median of the centers C, and STOPPING ORACLE(W,, T7) returns True if and only if the main part after W, contains at most |C,1/2 centers. The REBUILD operation is initially called for Ci. Next, for every node u where REBUILD has been called, we keep the number of centers ki, = |C..| contained in u at the timestep it was last rebuilt, and also track the number of updates (insertions/ / deletions) of since that timestep. If this counter exceeds / the operation REBUILD is called again at node u.
Rebuild:
LEEITION_LLFFFF
Insert: Suppose a new center is inserted. The algorithm calls GET EARLIEST CUT to find the carliest cut in the pre-generated sequence with its arrival time p that separates e from the anchor m.. Let (w/, p(). p.)...., (w/,., p(.) be the cuts currently used in this partition leaf call. Let p" be the stopping time assigned to this partition leaf call during its most recent rebuild. We consider three cases as follows: (1) p' for some j E [r]: (2) > p"; (3) p S p" and + pl for any j E [r].
Case (1): Assign this new center e to the node e generated by cut w/ and recursively maintain the partition leaf call rooted v.
Case (2): This new center c remains in the main part un until this partition leaf call ends. We then recursively maintain the partition leaf call on the main part un.
Case (3): It finds the smallest index j E [r] such that p < p¹, or sets j r if no such index exists. Then we insert this new cut w at position and add a new leaf node containing e to the tree.
Delete: Now suppose a center e C, is deleted. We locate the leaf node containing e in this partition leaf call. If this leaf contains only one center c, we remove both the leaf and the cut that created it. Otherwise, we delete from the leaf and maintain the next partition call recursively.
10

---

Acknowledgments and Disclosure of Funding
K. Makarychev and I. Papanikolaou were supported by the NSF Awards CCF-195533 and EECS- 2216970. We thank the anonymous reviewers for their insightful comments and constructive sugges- tions.
References
Sayan Bandyapadhyay, Fedor Fomin, Petr A Golovach, William Lochet, Nidhi Purohit, and Kirill Simonov. How to find good explamation for clustering? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3904 3912, 2022.
Sayan Bhattacharya, Martin Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering in o(k) update time. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering with fast update time and small recourse. In 2024 IEEE 65th Annual Symposium Foundations of Computer Science (FOCS), pages 216-227. IEEE, 2024.
Sayan Bhattacharya, Martín Costa, and Ermiya Farokhnejad. Fully dynamic k-median with near- optimal update time and recourse. Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1166-1177, 2025.
TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, pages 579-587, 2018.
Vincent Cohen-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Advances in Neural Information Processing Systems, 32, 2019.
Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. Explainable k-means and k-medians clustering. In Proceedings of the 37th International Conference on Machine Learning, pages 7055-7065, 2020.
Shichuan Deng, Jian Li, and Yuval Rabani. Approximation algorithms for clustering with dynamic points. Journal of Computer and System Sciences, 130:43-70, 2022.
Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Almost tight approximation algorithms for explainable clustering. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pages 2641-2663. SIAM, 2022.
Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson. Nearly-tight and oblivious algorithms for explainable clustering. Advances in Neural Information Processing Systems, 34:28929-28939, 2021.
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and Rachel Yuan. The price of explain- ability for clustering. arXiv preprint 23X4v22304.09743, 2023.
John Frank Charles Kingman. Poisson processes, volume 3. Clarendon Press, 1992.
Eduardo S Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In International Conference on Machine Learning, pages 5915-5925. PMLR, 2021.
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. International Conference on Machine Learning, pages 1984-1984. PMLR, 2017.
Konstantin Makarychev and Liren Shan. Near-optimal algorithms for explainable k-medians and k-means. In International Conference on Machine Learning, pages 7358-7367, PMLR, 2021.
Konstantin Makarychev and Liren Shan. Explainable k-means: don't be greedy, plant bigger trees! In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages (629-1642, 2022.
11

---

Konstantin Makarychev and Liren Shan. Random cuts are optimal for explainable k-medians. Advances in Neural Information Processing Systems. 36:66890- 36:66890-66001, 2023.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificcton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We provide complete proofs of all the claims we make in the abstract, intro- duction, and other sections of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [NA]
13

---

The performance of the algorithms is analyzed without making any assump- tions about the data.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide complete proofs of all our results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
SttsSSabmsiiooooiccoyooooi for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //n httpssscc/publcccucccccceco
/CodeSubmisse ieabbbmsssiiin ssssonoliccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/ httppp:////uuiis.... wwterrssscccpppeeeee wewbblic/thicssuideelee
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that this research was conducted accordance with
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work focuses on the development and analysis of approximation algo- rithms for explainable k-medians clustering under general l norms. does not develop any technology that has harmful or malicious applications. As such, we believe there are no direct negative societal impacts resulting from the work its current form.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
17

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thooe.. com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
18

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non noa-standard components.
Please refer to our LLM policy (https : /ttp///eeerppeeeeee cc/Conferences//20 /LLM) for what should or should not be described.
19

---

A Proofs in Section 3
A.1 Proofs Section 3.1
Lemma 3.4. Consider any partition call call node Let L. [2P+3 k). Then for every t 1, we have Pr( B > Re/2 Tr} S g
Proof of Lemma 3.4. Let Ct be the centers contained in the main part before the iteration of the partition leaf call. Then, we have C₁ C. be the set of centers contained in node u. Let m be the median centers in C.. Consider any center c C. with ||c - m > Re/ Suppose algorithm chooses the coordinate at iteration 1. Then, this center is separating from m at iteration t and only if oe = sgn(c, m and 0g E (0, |e mil). Thus, we have
c: m
Pr(c, m" are separated at t Te, i = i} =
2 R
Combining all coordinates, the probability that is separated from m² at iteration / is at least
Pr(c, m are separated at Tr)
Σ
Pr(c, m are separated at
Te, ft =
d
i=1
d
1
C4
m
||c
m
1
2d
R2
2d
RC
2d
2
20+1d
1=1
Since in one partition Ieaf call, the radius R2 is non-increasing as increases, for any iteration e' t. /2. Hence, conditioned on Te, if is not separated from m² before iteration t' 2 f, then is separated from m² iteration t' with probability least 1/2pt'a. Therefore, the probability that c is not separated from m" after L [2++3 In k]] iterations at most
we have ||c-m=Ilp > /2.
1
Se
20+1d
Since there most i centers with distance m greater than R,/2, by the union bound over all such centers, we have
Pr(Re+ > Re/2 Tx S
We show the following relation between the radius R. and the diameter D,, for each node u on which the algorithm calls the partition leaf.
Lemma 3.5 (Lemma 6.1 in Makarychev and Shan (2022)). For every node which the algorithm
calls partition leaf. we have Ra//4// < D. < 2R.
Proof of Lemma 3.5. is easy to get the second bound from the triangle incquality of the lp norm. Let m" be the median of centers in Cn,. We have for any two centers c' CT
||c llp S ||c m + I|m e'llp 2R...
We then show the first bound. For any function f C. + R. let avgrec. f(c) = To. be the average of f(c) over all centers in Cu. Let c' arg max ||c m" lpp be the center that is farthest from the median m" in Ep norm. For any pair of centers c, E Cu, the distance between c and é is at most the diameter of u, ēllp D... Thus, we have
- Eec,, (ce
D.. 2 avg,EC, ||c' - -cll,, = avg.gC.
Σ 14 2m
c
Σ avgaec, 10/ - csl..
20

---

Since m" is the output of GET DET_ANCHOF which always returns an approximate median of the centers in C.. least 1 of the centers c E C. lie on the opposite side of the hyperplane {z 2; = m } from the center d'. Thus, for these centers C.. we have Ic; - cal z cc m As result
d
1
D 2
BOEC, 14 cill
104 m
4 ||cl m 11, 4 Rey
1=1
1=1
which implies R Du
Lemma 3.6. For every node we have Rw/4//2 S Du S 2R
Proof of Lemma 3.6. For any node u which the algorithm calls the partition leaf, we have D.
D.. By Lemma 3.5, have R < D., S 2R..
We then consider any node u which is not a partition leaf call node. Let u be the node of partition leaf call that generates the node v. Since D. S 2Ru, we have D Rv Ru. S 2Rg Note that DN S 2 Thus, we have D < 2R, Since D,, 2 R., R2/44//, we have D2 2 D.. R. R., 2 R.,/4
0
We then show that D.. decreases exponentially along any path from the root to leaf in the tree. First, we show that any pair of centers that are far apart in the node are separated with high probability. Let Tu be the partial tree when node is generated in the algorithm.
Lemma A.1. For every two centers d' and e" in Cv distance at least Du/2.
1
Pr(d'è c" are separated at u Tw) 2 d 2
Proof. Suppose the algorithm picks coordinate at node u. For every two centers d' d' E Cu, we consider the following two cases: (1) c' and e" are on the same side of the median " in coordinate (2) d' and c" are on the opposite side of the median m on coordinate i.
For the first case, without loss of generality,
assume that of 4 2 mm Then, centers
e' and c" are separated by the cut at node u if and only if the algorithm picks d. = 1 and 6g e (c: m. of m.). Let Tu be the partial tree when node u is generated. Then, we have
(cf m (4 )
Pr(d, e" are separated at u in = =, Tw)
R
(c
c)P
2R
where the inequality is because x" convex and increasing on [0, 2o).
For the second case, d, and c" are on the opposite side of m Assume that df 2 m 2 c. Thus,
centers c' and c" are separated by the cut at node u if and only if a = +1,0 E (0, c m or 1,, E (0, c4 - m Thus, we have
Pr(c', c" are separated at 1/==0 = i, Tw.)
1
m
+ Ic m
Ry
|c' d/p/2PF-
2Rd
where the inequality is from (a² + b2/22 2 ((a ((a+b)) b)/2)p for a, 2 0 since x is convex on [0, oo).
Combining all coordinates, we have the probability that c' and c" are separated at node u is at least
14 c ||c" - -dp d(2R..))
Prfd', dl are separated Tw d
(2Ra)P
1=1
Since D. 2 R //, we have for every two centers
c, E C. with ||e" - c'llp D.,/2
R.
1
Pr(c', c" are separated Tw) 2
4 2
d(2Rn.)
2d
21

---

Lemma 3.7. Let L' = [
k]. For every node let node be any descendant of u at depth 6 d
L' in the free T. Then, have Pr D. 2 Du/2 Tw) S 33
Proof of Lemma 3.7. Let u' be the node at which the algorithm calls the partition leaf that generates the node v. Then, we consider two cases: (1) d(u', v) 2 4 L: (2) d(u',
< 4 L, where
L = dI k] used in Lemma 3.4.
In the first case, by Lemma 3.4, we have with probability at least (1 (1-11 11k3// 1 4/k² (where we used Beroulli's inequality),
RN
D
D', 2
D. S S
22
24
24
In the second case, we have d(u, w') 2 d(uu,)) - d(e, u²) 2 2n k. Thus, by Lemma A. we have every two centers in node u. at distance of least Du/2 are not separated at node u' with probability at most
2
(1
d. 22p+2
R5
By the union bound over all pairs of centers and all nodes, we have with probability at least 1 - 1/k2, all such pairs are separated at node u'. Thus, we have with probability least 1 4/k.
D. D. D. = D2 - 2
A.2 Proof of Lemma 3.3
Lemma 3.3. For some absolute constant / >> O, we have for any step t
cost (2, T) x To. (
2Aμ
+ 3 p(log k) - -og((AAAAA log² k).
E
Te < 3
+
k
Proof of Lemin 3.3. Fix arbitrary point X. Without loss of generality, suppose the step 1" = 1, which case (xx = e is the closest center to x C. Otherwise, if L" > 1, then conditioned on Ty-, we consider the subinstance consisting of centers that lie in the same leaf of Ti- as x.
We consider all steps in which the algorithm samples a cut to split the node containing x in the partial tree. With a slight abuse of notation, we index these steps by 1,...... Note that some of these sampled cuts may be rejected by the algorithm if they fail to separate any centers within the node. Let T, be the partially built tree before the cut step and let ue be the node containing xr in Te- The sequence of nodes u1 U2,... thus form path from the root to the leaf in the final tree T that contains x.? We divide the iterations into consecutive parts PI,... Ps. each corresponding the S partition leaf calls. Within each part P.. all steps / E P, for 1. E Ps occur in the same partition leaf call and share the same anchor point m.. Since the STOPPING OR ACI. ensures that for each PARTITION LEAF call, when partitioning stops, each leaf contains at most 7 fraction of the centers in its root for some constant 7 < 1, the number of partition leaf calls is bounded by Oloog k).
one of
Suppose that at step f, the point z and the center are contained in the same node i, before the cut applied. Let w; = (i. 0) be the cut selected by the algorithm at this step. We define the penalty oe (wr), or equivalently (i, 2), for the cut (i, 0) at step as follows. If x and are not separated by Otherwise, the penalty is given by
cut (i, f), then we set (1, 0)
(1 0) Elcost, T) Tr, = (i, 0) || - c
We now show two upper bounds on this penalty term. Conditioned on the partial tree Tr, know that in the final tree T. the point r must eventually be assigned to a center in Cu,, the set of centers
Some of the nodes in the path may appear multiple times in the sequence since certain cuts may be rejected by the algorithm, leaving the node containing unchanged.
22

---

contained in node By the triangle inequality, the final cost for æ is at most | clpp + Dr. where D, is the diameter node uy Thus, the penalty is most D,.. If x and are separated by cut (ú, 0) at iteration i, then we call the center c' closest to in u++1 as the fallback center. Define (1, :)) = x d'Ipp as the distance from x to its fallback center. By the definition of Ag. we have the penalty in this case is at most Ag Mf(i, v). Combining both bounds, we obtain se(i, 0) - min Dr, Me d)}.
Let L 12 d In k] and L' = [22 k1. We define the stopping time 7 to be the first step t such that one of the following events happens: (1) R. < | clpp: (2) x and e are separated by the
cut chosen at step i; (3) D. 2 D for t > I,; (4) Re 2 R L/2 for > L. We define four disjoint events as follows,
E1 (R, < || - cllr).
& {o and e are separated by the cut chosen step 7} \ E
E (D, D.- L/} (E)))))
. E4 RR+ 2 1.-1/2,5 L} (& (S
We call & good events and E3, & bad events. By Lemma 3.4 and 3.7, we have that the events &g and & happen with probability at most Pr[Ea} } < 1/k and Pr[E S 1/k. If either &3 or & occurs, we upper bound the expected cost of x in by A& || clpp since æ and remain unseparated step r. Therefore, the expected cost of point æ given by the tree T is at most
p/ T)] = E|cost (z, T) 1[2 U& + Elcost, (z, T) P
2 El (2. 7) (&, U & + Asl cllp
We then bound the expected cost of point x under the good events, E(cost, 7) 1( U
When the event & happens, we have and are not separated before step Since the diameters of nodes containing æ are non-increasing, the final cost for æ in this case can be bounded by
|| cllp D,
| cllp
2R,
3|1 cllp-
Thus, we have
(1 T) 1 < 3|1z - clp Pr(Ei} s - cllo-
-clp
We now turn to analyzing the event &g. We further partition this event based the step at which and c are first separated. For each step t 2 1, we define
εg11 = {ir and are separated by the cut chosen at step r & r == \
These events &2,1 disjoint and we have &g U121 &2,1. Therefore, the expected cost of under Es can be expressed as
Elcost, (z, 1(2))
Σ Elcost, 1(2,
We upper bound the expected cost of under event &g by Lemma A.2.
By combining all events E₁, E2, Eg, E4, we have that the expected cost of x is at most
Elcost (xr 7) E(cost,,(r, (s., 7) ({)))] + Efcost,(x, T) (( + Elcost, (z, T) 118 U&)]
2Ac
3 +
| <llp Σ E ((rr(ws) ((2
2Ac + p(log k)) +) L log(A A log" R:) ||x cllps
3
where 8 is an absolute constant. We now proceed to prove Lemma A.2.
23

---

Lemma A.2. For some absolute constant 3 > O, we have
Elor(wr) 1(E2,111 & B p(log k) - log(AA log² k)]l cllp-
Under the event E2, the point r and the center are separated by a cut. We classify the cut that separates z and e into three cases as follows. We first recall the definitions of light and heavy steps, as well as safe and unsafe cuts, given in Definitions 3.8 and 3.9.
Proof.
Fix parameter
which is specified later. We say that the step is light step if
Rs S Gogg k maxx m lp. ||c lll-mmm' m ml1b
where m' is the anchor of the node ut- Otherwise, call it heavy step. Furthermore, if the separates x and e at a light step, then we call a light cut; otherwise, it a heavy cut. Additionally, step we say that cut W/ = (i, 0) that separates x and is safe, if
R₂
A Az,
6 log k
Otherwise, we call this cut unsafe.
Then, we split the analysis into three cases: (1) safe cuts; (2) light and unsafe cuts; (3) heavy and unsafe cuts.
Case (Safe cuts): Suppose the event Ez, happens and x and are separated by a safe cut Wi = (i, 2). By definition, safe cut satisfies that the distance from to the fallback center c' after separation is significantly smaller than the current radius, specifically M, (i, 19) < R log" k). In this case,
we use A (e d)) as an upper bound on the penalty incurred by separating æ and c.
For each step i, coordinate i E {1,2, ... ,d), and direction a E {-1, 1,,1), 1), we define the safe cut set Rh
& (i, m + o0) separates and ej Gr,i = (0: Aa m² o0) 6 log
which contains all parameters E R such that the corresponding cut we (i, m; + o0) is safe. Then, the expected penalty due to safe cuts is at most
E (wr) [wr is safe} 1{E2,}]
(o + +z0,) 10, E Geino 1(2xt)
p. p-00-1
AsMi m + o0)
182,1)-- d0
2d Gu.s.
R
[=1
(-11)
McMili, m/ + of)
p p.gr-1
Σ
18 do.
2d Ge,t.
R
R RØ-1
1= (E(-1.1)
Here, the second inequality uses the fact that the coordinate i is chosen uniformly from 21, 2......... .d} and the direction is chosen uniformly from {-1, 1) and that is drawn from a distribution with density p00-1/ // R/. The safe cuts are those with 0 E Gt.....
Now derive upper bound for 8/ R2 to control the integral. Since center lies in node ue, have ||c - m² I < R,- Additionally, since the event ε, does not occur, we have Rg 2 || cllp- Using the triangle inequality, have
| m² 1pp
|| <llp
||c m'llp S 2R.
Therefore, have
3R;
|| m mI + ||c m
24

---

Furthermore, for any 0 E Gtas, the cut (i, m + a0) separates x and which implies
0 m max { [ mil, lc; m
Therefore, conditioned on the event 1 (( = 1, we have for any 0 E G..i.o.
0 3 max b mil, lcs ml
R₂
x mlI1p ||c ml
We now analyze each partition leaf call separately. Fix partition leaf call P.. Throughout this partition leaf call, the anchor m² stays the same. Thus, the expected penalty due to safe cuts within this call is at most
Σ t.P
(we(ws) 1(w is safe} 1(
3 max Jar mēl |c m
Σ
Σ
Ag (i, o0)
d0.
2d
(| m + |ce m= )
TEP, oEf-1,1) Gr.
Rg
By Hölder's inequality, the expected penalty above is at most
3 max [2 m.] le m m
p
2d
(||= - m² mn + |lc - m² 11,)
ArM,lim + o0) d0 1)
Σ
tEP, oE(-1.1) Guio
Rr
Then, we bound the two terms the above formula separately. First, we have
Σ
max mil lc- mi < ||0 mn + |le - m²Ip.
Thus, we have the first term is
Σ 3 max | m mn/b/cs lc: - m
3P-1
(| m² p + ||c m² (1p))
We now bound the second term. Note that for any fixed cut (i, I), the fallback distance M, 9) non-decreasing with respect to the step t. Meanwhile, within each partition leaf call P., the radius R2 is non- -on-increasing and decreases by factor of 2 after every L steps under event Ez. Therefore, for each coordinate i {1,2,-. ... ,d}, we have
Σ Σ
ES
Ag (i, m o0)
dd
sEP, LEP,OE(-IN 1111 G....
R
$
AsMa((i, m o0))
R₁ 110 E
Grao. d0
TEP, oE(-11(111
<4L
|x cil.
6 logo
where the last inequality follows from the definition of safe cuts, which ensures that A,M 0) < G T whenever 0 Gr..oo- and A (i.W) forms a geometric sequence increases by factor of Rr
every steps. Therefore, we have the second term is most
AsM m² o0). d0 /)
Σ
Σ
Σ
< 4L
6 log k ||0 cllp-
R4
IEPs oE -1,1] Grio
25

---

Since there are at most (llo k)) partition leaf calls and L [2 dd k|, the expected penalty due safe cuts is at most
(log k)
p 2d
.4L 33 6P log k | cllp55000 Op)) || - cllp.
1
Case (Light and unsafe cuts): In this case, we have that the radius R2 is relatively small compared to ||æ m lpp and ||c - m llp. specifically, R S 6 logg k max{|<æ - m²
mm'mlp llp. ||c - mm [p). Therefore,
in this case, we use D; 2R, as upper bound the penalty. Then, the expected penalty due to light and unsafe cut
E (dr(w)) {t light) 1 (wr is unsafe) 1{82,)] $
Σ
E [(ee(ws)
(
E [2R; 1 light) 1(2,,)).
1=1
For each step i, suppose both x and c are contained the node u1- We define the new event E as the event that either is first separated from the anchor m by the chosen at step t. To bound the expected penalty above, we show that
E ERR is light) 1[E2,t]] s log k. || cllp Σ E [ light) 1(E)))
To show this, define the stochastic process (Yi)220 as follows. Let Yo 0 and for any 2 1,
Y Σ (Re 1(2,,} - || cllp 24plog" k((E))) 1(t' is light).
We now show that this stochastic process (Y,):2n forms a supermartingale. Note that for each step l 2 1, we have
Y, = + (R& 1(8 || - cll, 24p log" 1(E)) 1ft is light).
step t heavy, then Y; = Y(-1- the following analysis, we focus on the case where is a light step and both æ and are contained in the node uz. In this case, we first analyze the probability that the chosen cut separates a and c, and the probability that separates either or from the anchor m
Claim A.3. Suppose both x and are contained in the node us at this step t. Then, the probability that x and are separated by the chosen cut is most
Pr(x and e are separated at step t Tx) < 2 - - c/ | m 11p-11111110110-10- ||c m m111-11
RC
The probability that either x or e is first separated from m' by the cut chosen at step t is at least
max max{[l
m² lpg
|lc m1]pp)
Pr[E (e) 2d
R.
Thus, we have for a light step f,
E|y,
Ti] Y--1 = RG Pr(E2,1
Tí) 24p log" k. ||0 clpp Pr(c- Te)
||x - m2 1 + ||c - m² 1--1 || cllp
12p log" h max of |
m mlpp ||c m m
d | c|l
P
R
d
R.
p d
max |
m² p ||c
ml
1--1 ()
6 6log* k max [| - m ml ||c m
<
| dlp
Ry
Rg
0,
26

---

where the last inequality follows from the definition of a light step. Therefore. {Yi is a su- permartingale. Hence, E[Yr] I E[Yo] for every fixed T. Since E|Yo] O, we have E E S and
T
T [Re is )ight) 1(82,{] & 24p k. || clp
Σ
Σ
E E 1
Letting
+ 0o, we obtain
Σ E [R light) 1(82,)] s 24plog" k. || clpp
Σ
El light) ((E))-
To bound the right-hand side, it suffices to control the expected number of times the event & occurs. Recall that & denotes the event that either or is first separated from the anchor m at step I.
We begin by noting that the number of partition-leaf calls is most Olog k). Within each partition- leaf call, the anchor point m' remains fixed, and once x is separated from m², it will no longer be involved in further cuts associated with that anchor. Therefore, can be separated from m in at most one step per partition-leaf call, contributing at most (log k) occurrences of E Additionally, observe that the center can be separated from the anchor m'' without x being separated most once. After such separation, e will no longer lie in the same node as æ and will not contribute to future events E.
Combining these observations, we conclude that the expected number of steps where E occurs is at most Ollog k), which yields
E Σ (wr) 1(t is light) 1 (ar is unsafe) 1{E2,) s (plogt +a k) || - cllp-
Case 3 (Heavy and unsafe cuts): Suppose the event E2 occurs and that and are separated by an unsafe cut W/ = (i, 2). For each step t, coordinate i E {1,2, ... d), and direction a E {-1, we define the the corresponding unsafe cut set
U2 { 00: 0 A,M, m o0) 62 log" k
R2
& (i, m² + o0) separates and e)
that is, the set of threshold 0 for which the cut (i, (i,m; + a0) is both unsafe and separates x from c. Let (t) = p((),..))) denote the Lebesgue measure of the set Ue and define 6,(t) (t. as the total measure across both directions for coordinate
Thus, the probability that wi is an unsafe cut is at most
[
0P-1
Pr(w: is unsafe}
do
2d JU
R2
max [1x - -mmmm lc - m
- 2d
RP
(=1
1ooe(111 1,1)
max{1
m/l lc-
m -1)()).
2d
R
In this case, we use the radius 2R, as the upper bound on the penalty for separating & and c. Therefore, the expected penalty incurred from heavy and unsafe cuts is bounded by
E (wi) 1w, is unsafe) 1ft is heavy) } 1(
E [2.R Priwe is unsafe} 1(t is heavy] 1(Eg,)}
max(
mfl. 14 - m
E
R
dc(t)
1 1ft is heavy) 1(E2r)
d
R
[=1
27

---

Since step t is heavy, we have R² 2 6log" k maxf[l m² llp. ||- 10-mmmlppp m'lpp), which implies
mmlpp.
1 ft is heavy) (6log" k-)=1 max { || mellp. || my melpp1 |
1
R
Substituting this into the previous bound, we obtain that the expected penalty in this case is at most
E (wrr 1w is unsafe} 1 is heavy) 1(
max mil |c: - m p--1
E
8t(() d
1(E2,)
l6 k)p-1 max || mellp: ||c me
1=1
Note that all steps within the same partition leaf call P. share the same anchor point. Let m denote the anchor point used in the partition leaf call P.. and define (s ΣiEp, d,(t). Then, the expected penalty above is at most
max [ - m7), lc; - m
E
(,(1)
(6 log k)p-1 max || m 11 p. |lc m p 1 1(2,tt
IEP,
1=1
8
max [r; me lcj m m pp-1
S
E
P
(8) (6 log kij-1 max || - m 1 ||c m p 1(82,})
Let (ss) denote the d-dimensional vector with coordinates (s(s) for i E (1,2, d]. Applying Hölder's inequality, we get
E (pr( I Mw, is unsafe) I is heavy) 1[8,,]]
+ DS |q mmpp)) 2-1
(2iz |r; - mppp) 1m:
E
P
[s)ll
(6log" k)p-1 max || m 1p ||c - m || p 1122)
d
| m 11 1 + ||c - m 1|
E
[ss)
m 10 p-1 118)}
d
(6log k:) max || m pps ||c
S
P
E
[+()))|>
1(8))
(6 log a k-
Finally, we use the following claim to bound the expected penalty.
Claim A.4. We have
Σ [a()) 188)} = =0
0 PPP.... d. d....
2og--b b k log(6P A log k)) || cllp-
By Claim A.4, we have that the expected penalty in this case is most
E
|a()) 1{E2,}
(6log kJp
O 4" d A--og=-- b k log(6" AA log² k)) || cllp
(6log k)p-ld
<0 (log k)2² 1 aa(--1 log( (A+ log" k)) || cllp-
Combining all three cases and setting = 1/p 1/2² we get the conclusion.
To complete the proof, prove Claim A.3 and A.4 below.
28

---

Proof of Claim A.3. We first analyze the probability that z and are separated by the cut chosen at step To bound the separation probability, we fix coordinate E {1,2, ,d} and consider the probability that the cut on coordinate separates and
the same side of anchor m' in coordinate i. Then, the threshold wi = (i, m + o0) separates and if and only if a has the same sign as m and 0 is between aar mil and [c; m Thus, the separation probability on this coordinate is at most
Suppose and
1 c ml Ir. m111 max [1 -mil m 1ipp-,, |cs m | -al:
2
R
R
where the inequality is from the mean value theorem.
Suppose and are on the opposite side of anchor m' in coordinate Then, the separation probability on this coordinate is at most
C3 m 1 Iz
mip
p. -max D mil
lc:
mm/0
11 - cal.
2
R
R
Combining all coordinates and applying Hölder's inequality, we obtain
p max (1r,
mmpp11 1,/c mppr-1)
la
csl
RV
d
| cllp
m/l"
+
Σ i=1
C2
mil"
d R
{ |
P
clpp
||
m
11p
+
||e.
m 111-1
R2
For point the probability that it is separated from m'' at step t is given by
r
m
P
|
m 1B
2d
R
2d
R
An identical argument applies to the center c, yielding the same expression with ||c mm]l Therefore, the probability that either æ or is separated from m'' by the threshold cut step f least
1 max m lp.. ||c m²1
2d
R
claimed.
To prove Claim A.4, we first show the following lemma.
Lemma A.5. For k vectors v², ... 2 E Edd that are entrywise non-negative, we have
Σ
H < k
Σ
Proof. We first upper bound the left-hand side. By Hölder's inequality, have
1. | S kd
1
= k'- r
|
We then lower bound the side. Since vectors vl ... w are nonnegative in every coordi- nate, we have for any coordinate j.
k
Σ
29

---

Combining all coordinates, we have
d
P
(0))
Σ
j=1
Combining the two parts, we get the conclusion.
Proof of Claim A.4. By Lemma A.5 and the number of partition Ieaf calls is at most (log k), have
E Σ
|b)
1(6)}
s (000og
E
Σ A
1{8,}
"
For any fixed coordinate i, we have
(s((s) Σ t,(t) SEL
Σ 5.(t)
110 E Una1dd0 /1 U1,.-1)00. Σ
We now show that each cut w (i, 8) that separates a and is unsafe at most L" = L' log(6P. Aş- log" k) steps. Consider any cut w = (i, i)) that separates and c. This cut w is unsafe at step t and only if R2 S 6" log" k A (2, 8). For every step t, by the triangle inequality, the penalty to the fallback center is at most M, 0) S D; < Dr. We know that M,(i, d) is non non-decreasing as increases. Let tu be the first step when is unsafe. Let t be the last step when w is unsafe. Then, by the definition of unsafe cut, we have Re,, S 6" log" k Mr (2, 0). Then, we have
R.. 6". logg k- Av
De, 2 Me
Mc (w) 2
Since R//4 D. 2R, we have
R
De.
De, 6" log k
2
A
2. 6D log" k Ak
By Lemma 3.7, we have Dr decreases by a factor of 2 after I' 222 6d steps. Thus, we have that the number of unsafe steps is at most
tw L' 1ogg(2 6" log² k Ax) 0(P d log k plog(As log² k)).
Therefore, have that when the event Eg happens,
(s) 0 d log k log(6" A log k))]a;;; cil-
Hence, combining coordinates, we have
s
E
Σ
(s)
1(2)}
0(4 d. log log(6p Ag log² k)) lx - cllp:
which completes the proof.
B Dynamic algorithm implementation and analysis
In this section, we provide the full description of the dynamic algorithm, along with an analysis of its approximation guarantee, update time, and recourse.
30

---

B.1 Dynamic algorithm and approximation guarantee
We begin by presenting the detailed dynamic algorithm and proving that, after each update, the distribution of its output is equivalent to that of corresponding static algorithm.
Lemma B.1. Given sequence of k requests, where each request is either insertion deletion of single center, let Te be the threshold tree maintained by the dynamic algorithm for the center set LEETIONNLEAFFFEE C.. Let Ti be the tree constructed by the static algorithm PARTITION LEAF (Figure with specific
oracles centers Ct. Then, the two trees are identically distributed T d T!
The following corollary is immediate from Lemma B.1 and Theorem 3.1.
Corollary B.2. Given sequence of requests, where each request is either an insertion or deletion of single center, the dynamic algorithm provides a threshold tree Te for each center set Ct such that for any set of points X,
E cost, (X, Ti)] - =0
- (p(log ki) - log log ki) costp (X,t,(X,Ci) Ci),
where k, |Crl
We provide a dynamic implementation of the PARTITION LEAF procedure in Figure 2, which is applied recursively to obtain a fully dynamic version of the entire clustering algorithm. The dynamic variant of PARTITION LEAF supports three operations: (1) REBUILD, (2) INSERT CENTER, and (3) DELETE CENTER.
We begin with the REBUILD operation, which reconstructs the subtree from scratch using the PARTITION_ _EAF procedure as follows.
Reconstruct the subtree rooted at node u, partitioning all centers in C into distinct leaves via recursive calls to the PARTITION LEAF procedure. During each such PARTITION_LEA call on node v in this operation, the following oracle outputs are used and remain fixed throughout subsequent updates until the next rebuild:
REBUILD:
GET GET_ANe ANCHOR sets the anchor m" as the coordinate-wis median of centers in C.-
SToPpING_ ORACIE COOPPING_ORACCLEOOO determines whether to stop accepting further cuts based on a stopping time p². It returns True if and only if the the timestamp of the input cut w satisfies p >> p². The stopping time p" is defined during the rebuild as the timestamp the last accepted cut such that the main part uo contains at most half of centers in C., i.c. 1C S 1C,1/2.
We now describe the condition under which the rebuild operation is triggered in the dynamic algorithm. Let be the node on which this operation is applied. Suppose a center e inserted into or deleted from the set of centers assigned to u. For each partition leaf call, we maintain a counter that tracks the number such updates since the last rebuild. Let K' be the number of centers in node u at the time of the last rebuild. When the update count exceeds k'/4 /4, we rebuild the partial tree rooted at node
We now proceed to handle the update.
INSERT CENTER: Suppose a new center e is inserted in the subtree rooted at node u. The algorithm calls GET EARLIEST CUT to find the earliest cut in the pre-generated sequence with its arrival time o that separates e from the anchor m Let pi)..... (w/,, pf) be the cuts currently used in this partition leaf call. Let nM be the stopping time assigned this partition leaf call during its most recent rebuild. We consider three cases as follows: (1) = p for some j E [r): (2) (3) < p" and p + p' for any E [r].
Case (1): Assign this new center e to the node v generated by cut w/ and recursively maintain the partition leaf call rooted
Case (2): This new center e remains in the main part un until this partition leaf call ends. We then recursively maintain the partition leaf call on the main part ug.
Case (3): It finds the smallest index j [r] such that p p', or sets j r + if no such index exists. Then we insert this new cut w at position j and add a new leaf node containing e to the tree.
Now suppose center E C, is deleted. We locate the leaf node containing in this partition leaf call. If this leaf contains only one center c, we remove both the leaf and the cut that created it. Otherwise, we delete from the leaf and maintain the next partition call recursively.
DELETE CENTER:
31

---

Algorithm DYNAMIC PARTITION_LAE
Input: A sequence of updates Q = (gL: q2. q2....). where each qe either: (NSERT(C): insert new center e RR DELFTE(e): delete center c. Output: For each update in Q, maintain a threshold tree Ti over the current center set C₁. Main(Q):
1. Initialize the root be empty.
2. For each update dr at time t:
If de is INSERT(C): call INSERT_CENTER(C.) r) where r is the root.
If (j is DELETT((C:: call DELETE_CENTER( (c, r) where is the root.
Output the updated tree Tz.
Procedure REBUILD(U):
Let C₂ be the current center set u, set anchor m" be the coordinate-wise median of centers C., Initialize the main part ug = u.
2. Initialize an update counter at u to be Cnt,, = O and set k., = |Cal-
3. Compute sequence of candidate cuts {(wi, pt)] using an exponential clock:
For each I, sample i, E [d], E {-1,1}. Ze Unif(0, 2n). Define the cut (iz, 0z). where d, mi, +or(Z,) Assign the timestamps Pr the arrival times of a Poisson process.
4. Iterate over the cuts wi in increasing order of their timestamps Pt. Accept iff wi separates two centers in the main part ug- After each accepted cut, update the main part Up the side containing the anchor. Stop when the main part contains fewer than [Cul/2 centers. Then, set the stopping time p" to be the timestamp of the last accepted cut,
/² = max (pr cut wi is accepted).
5. Call REBCI.D(V) for each leaf v containing more than one center the subtree rooted at
Procedure INSERT INSERT_CENTERR CENTER(C, u):
Increment update counter at u; updates exceed k call REBUILD(U).
2. Get the earliest (w,p) p) GET EARLIEST_RLULTTT that separates and m".
3. Let (w). (w/, p`.) be cuts used by and p" be the stopping time.
4. If p = plj for some j:
Assign to node u separated by the cut w/. and call ANSERT_CENTERR v).
5. If p > p": Assign e the main part wg. and call INSERT INSERT_CENTER( CENTER un).
6. If p S and p p', for every j:
Insert new cut w into the sequence of cuts used by u, maintaining increasing order
by p. Create new leaf node containing c, and attach it to the tree the cut point.
32

---

Procedure DELETE CENTER u):
1. Increment update counter at u; if updates exceed k,/4, call REBUILD(U).
2. Locate the leaf node v containing c.
3. If the leaf contains only c: Remove both the leaf and its parent cut.
4. Else: Delete from the leaf and call DELETE_ CLALEE_CENTER(:22 v).
Figure 2: Dynamic algorithm for explainable k-medians in
Proof of Lemma B.I. We describe implementation of the static algorithm on the set of centers C2. using specific oracles BET_ANCHOR and STOPPING_ORACLE
To couple with the dynamic algorithm, mirror each partition leaf call currently maintained in the dynamic algorithm solution. We begin with the partition leaf call at the root node. Let < denote the time of the most recent rebuild of this root partition leaf of time t, and let k |Cerl be the number centers present at that rebuild time. Assume both the dynamic and static algorithms use the same infinite sequence of candidate cuts with associated timestamps for the root PARTITION_LAE _EAF call.
For any fixed sequence of cuts with timestamps, let m' be the anchor and p" be the stopping time used by the dynamic algorithm for this root partition leaf. In the static algorithm, we adopt the same oracles the dynamic one: the oracle GET_ANCHOP returns m and STOPPING ORACLE returns True if and only the timestamp of the input cut exceeds p". As a result, the static algorithm accepts exactly the same sequence of cuts the dynamic algorithm. Therefore, the partial tree rooted at produced by this PARTITION LEAF call in the static algorithm is identical to that maintained by the dynamic algorithm. We will show that these oracles are valid for the static algorithm, which means they satisfy the required properties in Section 2.
We first show that GET_ ANCHOR returns approximate median of centers C.. Because this is the most recent rebuild of the root node r, there have been fewer than / updates since then. Note that the anchor m² is chosen the coordinate-wis wise median of all centers in Cr at time f'. For each coordinate i, at most half of the centers in Cp lie on either side of m". Hence, even after ke /4 updates, there remain at most 3k, 4 centers in C either side of m² along every coordinate." Therefore, the anchor m" remains an approximate median for the current set of centers Ct.
We next show that the STOPPING_ ORACLE guarantees that when partitioning stops, every leaf contains most 3/4 fraction of centers C. Consider any leaf that separated from the main part during the partitioning. Each such leaf contains only centers that lie on one side of the anchor m² along the coordinate used by the cut that separates Since the anchor m" an approximate median of centers in Ct at most 3k/4 centers lie on either side of m² along every coordinate. Therefore, each separated leaf contains at most a 3/4 fraction centers in C.. As for the main part, recall that at the stopping time p" during the last rebuild, it contains most ky 2 centers in Cp. After at most ky /4 updates, the main part contains at most a 3/4 fraction of centers Ct.
At each recursive step, we use the same sequence of cuts and adopt the corresponding anchor and stopping time used by the dynamic algorithm. This guarantees that the static algorithm mirrors the behavior of the dynamic one at every level of the recursion. Therefore, the static algorithm constructs exactly the same threshold tree as the dynamic algorithm. This completes the coupling argument and establishes that the output of the dynamic algorithm is identically distributed to that of the static algorithm on input C,,
*Consider any fixed coordinate and one side of m.. The fracttin of centers lying on this side of m² maximized when all kg/ /4 updates remove centers from the opposite side. Thus, the fraction of centers lying on this side is most 2/3 after updates.
33

---

B.2 Efficient implementation and analysis
In this section, we present practical implementation of dynamic algorithm as shown in Figure 2. We evaluate the efficiency of the algorithm from two perspectives: update time and recourse.
First, the update time request 9, refers to the time required to modify the threshold tree Ti-1 in response to the 1-th request (either an insertion or deletion of a center), resulting in a new tree Ti- Second, the recourse at request qe is defined to he the number of nodes that differ between Ti-1 and Tr i.e., the size of their symmetric difference hetween the two trees.
We focus on bounding these quantities in the amortized sense, i.e. the total update time and total recourse over all requests, averaged across the requests. The following lemma summarizes the performance guarantees of the dynamic algorithm.
Lemma B.3. Given a sequence of requests, where each request is either an insertion or a deletion of single center, the dynamic algorithm satisfies with probability 1 the following guarantees for every t t2l
1. the amortized recourse is O(log k).
2. the amortized update time (dd log k))
where k- = max |C,).
We first describe efficient implementation of the dynamic algorithm. For each node where REBUIL. is called, we maintain a self-balancinn binary search tree that stores all cuts with timestamps (wi, p1), (wo- .. (w/,- used in the partial tree rooted at This data structure enables efficient BERLIEST_CURe
updates. When a new request arrives to insert or delete center c, we call to compute the earliest cut that separates from the anchor m n. and then search the binary search tree to locate where this separation occurs in the partition leaf path of u.
We now describe an efficient implementation of the function GET EARLIEST CUT. Without loss of generality, we assume that all centers are in 1|.. The function GET EARLIEST ___ takes center as input and outputs the earliest cut (w, that separates from the anchor m" among sequence of candidate cuts (wi, P1), (w2, P2),... Each cut W/ = (i,, 0,) is generated by sampling
coordinate sign E {-1.1) uniformly at random, and parameter 0 E [0, 2] drawn from the distribution with density f(x) = pxr-1/22 The threshold is then set as 0, = m + at. The associated timestamps pr follow the arrival times of Poisson Process with rate 1.
To facilitate efficient implementation, we first observe that the problem naturally decomposes across coordinates. Specifically, for each coordinate i E 2,,,2... d). we can independently maintain and query the earliest cut that separates e from m along coordinate i. We then return the cut with the minimum timestamp across all coordinates.
To achieve this, we maintain an independent stream of candidate cuts for each pair of coordinate
and direction {-1, 1). 1). Each such stream consists of cuts = (i, 0) where 0 = m + a0 and the timestamps given by the arrival times Poisson process with rate 1/24. This decomposition formally justified by the Coloring Theorem (see, e.g. Kingman (1992), page 53 or Mitzenmacher and
Upfal (2017), page 223), which states:
Theorem B.4 (Coloring Theorem). Let 11, be a Poisson process the real line with rate X. Assign to each event of the process a color from a finite set (1...., M), where each event is independently colored with probability pt of receiving color i. Then the counts of events of each color, I1,".. M.. form independent Poisson processes, with rates Apr, XPMM respectively.
The original sequence of candidate cuts has timestamps given by the arrival times of Poisson process with rate 1. Each cut independently assigned a pair (i, a) with uniform probability 1/2d over all 2d possible combinations. By the Coloring Theorem, the subset of cuts corresponding to any fixed pair (i, o) forms an independent Poisson process with rate 1/2d and these 2d streams are independent. Therefore, the union of all these subsequences of cuts has the same distribution the original sequence of candidate cuts.
We then formulate the earliest cut along each coordinate as the following general problem. We are given a fixed anchor value m E [-1, 1]. and sequence random euts specified by thresholds i, drawn from [m, + 2] according to probability density function f(z), with associated timestamps
34

---

Pt. corresponding to the arrival times of Poisson process with rate Ag. For a query point E [m, 1), we aim to find the earliest cut that separates y and m, i.e., the cut with the smallest timestamp such that its threshold 02 lies in (m, v). This formulation arises naturally in our setting, where λo = 1/24, the density function f(x) = p(æ - m) m)--1/2 /2P, m represents the i-th coordinate of the anchor, and y corresponds to the i-th coordinate of some center c. A simple approach for solving this problem is to simulate the sequence of cuts with timestamps and return the first one that lies in (m, y). We refer to this as the static algorithm.
We now describe a data structure that efficiently retrieves the earliest cut along a given coordinate. This data structure maintains self- taflbcaanning binary search tree. Given an anchor m and a set of k values m S 1/1 < y/2 < < yk S 1, this binary search tree maintains these values in increasing order. Each node in the binary search tree stores value y along with the earliest cut that separates from the anchor m, including the timestamp of that cut. If the queried value y is present in the tree, the associated earliest separating cut can be retrieved in Oloog k) time.
Now suppose we need to insert a new value y E [m, 1] into this data structure. Assume the binary search tree currently stores k values m S. 91 < y2 < .... < y/ S 1. We first locate the position of in the tree in Ollog k) time, either identifying the smallest index j such that y < yj, or determining that y > Let retrieve the earliest cut (0. p) that separates yj from m. We consider two different cases:
m. If there exists some 1 S j S k such that V/-1 < < My. then we first
1. 11 < < My for some 1 j.j S k and (0,p) also separates y from m, (i.e. 0 S y):
2. either y/-1 < < yj and (9, p) does not separates y from m (i.e. > y) or yss < y S 1.
For the first case, we store this cut (0, p) at the node y as the earliest cut that separates y from m. For the second case, we first sample a new cut as follows. If y 2 yk. then let yj-1 = y/. Sample new threshold s' E [1]-1,3] using the weighted density function
f(x)
f(z)
f(x) = Pr(0 E 11 f M())( IE (1)-1.9).
We then sample a timestamp for this cut as pf = =p= 2, y S yks otherwise if y > yks p 2, where 2 ~ exp(A) with rate
[" f(t)dt, Ao Pr(d (15-1, w13 = 2o J,,
where do is parameter of the data structure. Let (0", be the carliest cut that separates y/-1 from m. We then compare the two cuts and store node y the one with the smaller timestamp. If p' p", then we store the new cut (0', p¹) at node y as the earliest cut; otherwise, we store the cut (0", ,""). Lemma B.5. Given a sequence of query points y1: "",,.., the earliest cuts maintained by the data structure are distributed identically to those returned by the static algorithm.
Proof. We prove this lemma by induction. For the first query point, the data structure and the static algorithm samples the earliest cut that separates this point from the same distribution. We now assume that for the first & query points y1, ykk the earliest cuts returned by the data structure are distributed identically to those returned by the static algorithm. By coupling these two algorithms, we further assume that the data structure and the static algorithm return exactly the same earliest cuts for these query points.
We now consider a new query point yk41 and argue that the earliest cuts returned by two algorithms are distributed identically. Let y(1), (*2). , Miik be the first k query points sorted in increasing order. Let M(0) = m. Suppose this new query point is in the first case, which means there exists 1 و S k such that 1))-1) < Mk+1 < B(y) and the carliest cut (0,, pt) that separates V()) maintained by the data structure also separates yk411 Since #k+1 < (()) and this cut (0,, Pt) is the earliest cut that separates (G) in the static algorithm, this cut is also the earliest cut for yk+1 returned by the static algorithm.
We now consider this new query point is in the second case, either 1(--1) < yk41 < V()) and the earliest cut (0r, pt) that separates (()) does not separates + 1 or ((k) < yk++1 S 1. If yk+11 > y(k) we set D1)1) y(k)- We decompose the sequence of cuts used in the static algorithm into three
35

---

disjoint subsequences. These three subsequences contain all cuts in three disjoint intervals (m, Mij M1j- (MGj-)), 1k+1], and (yK+1, m + 2] respectively. By the Coloring Theorem, the timestamps of these subsequences follow the arrival times of three independent Poisson processes. Since the cut is sampled from (M(--1)> M6+11 with probability p = - f(t)dt, the timestamps of all cuts in (V(y-)), Me++1 follows the arrival times of a Poisson process with rate
f s())d).
X = Ao Pr(0 E (11s-1), Me+1]} Ao
(13-1)
Suppose there exists 1 S S such that 115-1) < yi+1 < y Since the earliest cut (0t.Pt) that separates yG) does not separate yi++1 in the static algorithm, the first cut in the interval (f(z-1), 1), Mk++1 must arrive after Pt. The time of the first arrival of this subsequence follows an exponential distribution with rate X. Due to the memoryless property of the exponential distribution, the first arrival of cuts in (M(j-)) 1). 1 follows Pt 2, where 2 ~ eXp(A). Suppose Me+1 > V(k). Then, the time of the first arrival in this subsequence is a ~ exp(A). Therefore, in the static algorithm, the first cut in (30-1)) 9k++1] has the exact same distribution as the new cut sampled in the data structure. If U(j-1) * m, then the first cut in (m. 11) is the same in the data structure and the static algorithm. Combining two parts, the earliest cut that separates yk++1 returned by the data structure has the same distribution as that returned by the static algorithm.
Remark. The assumption that all centers lie in [-1, 1j2 is made for the ease of exposition. The algorithm can be implemented without this assumption. Under the e, norm, the threshold 0 is drawn from a distribution with density fxx) = pz="1// /R" where > y is the bounding radius. Conditioned on x E (yj-1. the probability density function becomes
f(x) f(z) (") (y - m)" (y)-1 m)p
p(u m)p-1
To sample a threshold 8' following this distribution, we draw uniform random variable U [Vy,- m)" (y- m) and set v' = UL//, Moreover, multiplying all timestamps by the same positive number does not affect the analysis of B.5. Thus, we can equivalently sample = ~ exp(A) with o = (y m)" (yj-1 m),, without altering the analysis. With these minor modifications, the algorithm no longer depends the boundedness assumption that the centers lie in [-1,
We now analyze the recourse and the update time of the dynamic algorithm with the above implemen- tation.
Proof of Lemma B.3. Fix f 2 1 and condition the randomness of the algorithm until time t. Since the subsequent argument holds for any fixed randomness, the guarantees hold with probability 1.
Recourse: Let R(()) be the recourse incurred by request i. We partition the requests into two sets: Let S₁ S [t] be the set of requests for which the REBUILD operation not called during the update due to this request. Let Sg = [t] \ S be the remaining requests where the REBUILD operation is called. We analyze each case separately.
Case (i E S)): In this case, the request does not trigger REBUILD operation, and the recourse is at most R(1) < 2. This is because if the request is an insertion, at most two nodes are added T--1; if it is deletion, at most two nodes are removed, i.e., the leaf that contains the center e and its parent in both cases. As a result, the total recourse over all such requests is bounded by
Σ Rii < 2|S S 21. VESI
(2)
Case 2 (i E S2): The REBUILD will only be called on one node u; for each request i. Let Cu,, be the set of centers contained in the node u, of T--1, and let K' = |Cu, Since REBUILD(U)) is called, all 2k' - 1 nodes in the subtree rooted at ti are removed from T:-1- If the request is an insertion of a center c, a new threshold tree is constructed at u, using the updated center set C., U {c), which has size k'' +1 1. This results in inserting 2(k' + +1)
= 2 + 1 nodes back into the tree. Therefore, the
recourse is R())= = 2k' - 1 + 2 + 4k' If the request a deletion of a center e, the updated center set is Cup \ of size k' 1, and the rebuilt threshold tree contains 2(k' - 1) 1 2k' 3
36

---

nodes. The recourse in this case is R(2) = (2K' - 1) + (2k' - 3) = 4k' 4. In either case, we have the bound R())= I 4k'
We now analyze the total recourse for S2. Each node u on which the algorithm calls a REBUILD stores an update counter Cnt.,- This update counter is initialized zero when the node is rebuilt and is incremented by one each time an update (insertion or deletion) involves node u. This node also stores the number of centers kn in this node when it rebuilt. Since the dynamic algorithm rebuilds this node after / updates, we have k' Hence, we have
I ku + kw/4. Therefore, we have Cnt,, = k K //5
R( S Σ
20 20- (us)
(3)
VES2
$ES.
The right-band side of (3) is bounded by the total number of times any node's counter is incremented. According to the analysis in Lemma B.I, the dynamic algorithm guarantees that after the partition leaf call of node u, each leaf has at most 3/4 fraction of the centers contained in Let = max |Cal be the maximum number of centers during the first t requests. Therefore, each update request involved in at most (log k) calls of INSERT CENTER or DELETE CENTER. Thus, DELETE_CENTER.
INSERT_CENTER
the total number of times any node's ' counter is incremented bounded by O log k). Combining this with (2) and (3), we conclude that Σ R(1)= = O log k) and thus the amortized recourse is Olog k).
Update Time: As in the amortized recourse analysis, let S S [t] be the set of time steps where REBUILD is called
node U; and let S2 [t] \ S1. We now split the analysis into two cases, depending on whether or not a rebuild is triggered.
Case (i E Sj): Suppose the request is insertion of center c; Let u1, U2..... ................................ be the nodes for which INSERT CENTER (c;, Uy) is called. Each such call on node u takes O log k) time, where k max [C,]. It takes
(d log k) time update the self-balancing binary search trees stored in u;
(d log k) time compute the earliest cut through GET EARLIEST_CUTIÇ CUT(c:);
Ollg k) time to locate this earliest cut and insert the center by searching the self-balancing binary search tree that maintains all cuts (wi, p1), (w/, p2)..... (w/, pf)) currently used in the partition leaf call of u.
Since the center e; is involved in most Ollog k) INSERT_CENTER calls, the update time for an insertion request Sj is Time(i) = (d log" k)). The same asymptotic bound holds for deletions, as finding the leaf that contains the deletion center e; takes Odd k) time, and the removal takes constant time. Thus, we have
Σ VES,
Time(i) = ((S) -logg k))
Case (i E 52): Let uq be the node that is rebuilt at request i. As in Case 1, the time to process the request before the rebuild is (dg k). If u, contains k'' centers at this request i, then REBUILD(Us) takes Ol'' d doog? k) time.
Since when REBUI.D(w:) is triggered, we have the update counter Cnta; 2 k/55. Thus, we charge the rebuild time to the update counter. That is the update time Time(i) < O(Cnt., dlogg k). Therefore, we have
Σ Time(i) & Od k). Σ Cut 2
(5)
i
By the analysis in recourse, we have Eies, Cutu, 5 O k). Combining (4) and (5), we obtain that the total update time is at most
Time(i) Old k)
and the amortized update time is Od k).
37

---

We now prove the main theorem of the dynamic algorithm.
Proof of Theorem 5.1. By Corollary B.2 and Lemma B.3, we get the approximation guarantee, amortized recourse, and the amortized update time of the dynamic algorithm.
B.3 Fully Dynamic Explainable Clustering Algorithm
In this section, we provide a fully dynamic explainable clustering algorithm for the setting in which the clustering data set evolves over time through insertions or deletions of data points. This algorithm maintains an explainable k-clustering that is competitive against the optimal (unconstrained) k- clustering. This setting contrasts with Sections B.1 and B.2, where the cluster centers change over time.
Formally, the input is a stream of updates on the data set, where each update an insertion or deletion of data point. This generates a sequence of datasets X1, X2..... If t is insertion request of new data point Zt, then X, = X,-1 U { whereas f is a deletion request of an existing data point I, Xt-1, then X, X \ {mz) }. We obtain our fully dynamic explainable clustering algorithm by combining our dynamic algorithm from Section 5 with the fully dynamic k-medians algorithm of Bhattacharya et al. (2025). This fully dynamic k k-medians algorithm maintains constant-facte approximation while changing only ((1) centers per update.
Corollary B.6. Given positive integer k and a stream of updates that are insertion deletion requests of data points TRd, for every p 2 there exists a fully-dynamic explainable clustering algorithu that outputs threshold tree Te for every t 2 1 satisfying
1. (Xcostp(X,, (X,TT)) S (pllog k)
- log loglog OPTx.,(X.).
2. the expected amortized update time is Ö(kd + (log A) k).
3. the expected amortized recourse is O(log A) log
where A is the aspect ratio' of all data points in X = Ui-1 X, OPT is the Ep cost of an optimal (unconstrained)) k-medians clustering of X, and Ô hides polylogarihmii factors in A, k and
= |X]
To prove Corollary B.6, we first show how to combine any fully-dynamic (unconstrained) k-medians clustering algorithm under the Ep norm with our dynamic algorithm from Section 5 to get a fully- dynamic explainable clustering algorithm.
Definition B.7.
an (a, v. dynamic k-medians clustering algorithum under the lp norm, for every stream of updates that are insertion or deletion requests of data points, the algorithm outputs i centers C₁ after each update t, such that (X,, Tt) S OP.),(X.). the expected amortized update time is and the expected amortized recourse is r.
An algorithmm
Fix an iteration t of an (a, u, r) dynamic k-medians clustering algorithm under the Ep norm for 2 1. After processing the f-th update request, the algorithm updates the current set of centers from Ct-1 to C.. To apply Theorem 5.1, we treat each E C.-1 \ C2 as a deletion from the current center set G and each e C. C--1 as insertion into it. Algorithm formalizes this procedure, and its performance guarantees are proved in Proposition B.8.
Proposition B.8. Given a positive integer k a stream of updates that are insertion or deletion requests of data points in Rd and an (a, u, dynamic k-medians clustering algorithun A under the Ep norm for some 2 1, Algorithm outputs a threshold tree for every time t. ' 1 satisfying
(a-pplog 1. Elcost, (Xcost,(,,,) X,, T.) S (a- p(log k) 1+ log log k OPTRp((X))
2. the expected amortized update time O(u + r dlogs k)
3. the expected amortized recourse O(T log
*The aspect ratio of set of points X under lp norm is A
max I|r-vll,
min waatt
38

---

Algorithm FULLY DYNAMIC PARTITION LEAF DYNAMMCCPARTIIIONN
Input: integer k;, number 1, stream of update requests of data points ạ1, 92, and an (a, u, r)) dynamic k-medians clustering algorithm A under the Ep norm. Output: threshold trees Ti, .
1. Initialize the root root to empty.
2. Initialize Co to be empty of centers.
3. For every t 1:
Run algorithm A to process request and get new set of centers C₁.
For every center Ct-1 \. Cz:
Call DELETE_ COLETE_CENTER(; rool) in Figure 2.
For every center с E C Ct-1:
Call INSERT (CENTE((C root) in Figure 2.
Output the threshold tree Tj rooted root.
Figure 3: Fully Dynamic algorithm for explainable k-medians in lp
Before we prove Proposition B.8, we show how it yields Corollary B.6 by choosing the fully dynamic k-medians algorithm by Bhattacharya al. (2025).
Proof of Corollary B.6. The dynamic algorithm for k-medians from Bhattacharya et al. (2025) achieves an O(1) approximation. It has O(log² A) expected amortized recourse and O ex- pected amortized update time.' As result, by Proposition B.8, we get the conclusion.
We proceed to prove Proposition B.8.
Proof of Proposition B.8. Fix any 2 For every i E (1,2..... let C, denote the of centers produced by A after processing the i-th request. Let 10, denote the recourse time During iteration i. Algorithm 3 produces T; intermediate center sets C¹ C Cg......, Ch,,, = C corresponding the individual center update requests applied to C. Since deletions are processed before insertions, each intermediate set has size at most k. Let T( ........ Thr denote the intermediate threshold trees produced by Algorithm 3 after each center update during iteration i. For the rest of the proof, we condition on a fixed sequence center sets C₁,,, C. Cr,,, = Ct.
Approximation: Applying Theorem 5.1, for every (1.2,....f) f} and E (1,2..... rz) the following inequality holds:
Elcost,, (X,, (x, Ch,1...., C,,,, O (p(log)) 1+ loglogk cost pX, Cly).
Therefore, choosing j Tz we obtain
(X,, Tz) Ci,
O (plog ( - log log k) cost, Ct).
Taking the expectation at both sides of the inequality and using the fact that A is an a-approximation algorithm, the approximation guarantee follows.
Recourse: By Theorem 5.1, the amortized recourse of DYNAMIC, PARTITION LEAF is O k) with probability 1. Hence, after processing t requests, the total number of tree nodes modified is O(R k), where R Ei=1 denotes the total recourse of algorithm A, i.e., the total number of center update requests. Therefore, the expected total number tree nodes modified up to the t-th request O (EE log k) O(rt log k), which corresponds to the expected total recourse. Dividing by t, we obtain the expected amortized recourse of O(r log k).
DYNAMIC_PARTITIONN
'The algorithm introduced in Bhattacharya et al. (2025) is aimed for the metric k-medians problem and it's amortized update time is Ö(k). For our purposes, the amortized update incurs an extra ( factor to calculate the & distances. Ô hides polylogarithmic factors in n, A, and k.
39

---

The total update time of Algorithm 3 equals the sum of the running time of A for pro- cessing all requests and the time taken by DYNAMIC_ PAAMMIIC_PRRIIOONN_N LEETFI to handle all R = Ei= r; center update requests. By Theorem 1. the amortized update time of DYNAMIC_PARTTIONN_ PARTITION_LEAA is Ogd k) with probability 1. Thus, the total update time is O(U + Rdlog" k). where U = Ei=1 u the total running time of A. Since the expected amortized update time and recourse of A are u and r respectively, the total expected update time of Algorithm 3 is Out + rt d log" k) and the expected amortized update time guarantee follows.
Update Time:
C Lower bound for universal algorithms
In this section, we provide lower bound on the competitive ratio for any universal explainable clustering algorithm. A universal algorithm is required to output distribution over threshold trees that perform well for all p 2 1 without the prior knowledge of p.
Our algorithm for explainable k-medians clustering under Lp norm samples threshold cuts from a carefully designed distribution that depends crucially on p. A natural question is whether there exists an explainable clustering algorithm that is independent of p while achieving a good approximation to the optimal lp cost for all simultaneously. We answer this question in the negative by showing an (dd/aa) lower bound on the worst-case competitive ratio of any universal explainable clustering algorithm.
Theorem 4.2. There exists an instance X C Rdd such that for any distribution over threshold trees, the expected competitive ratio is at least ((dd/AA) for some p 2
0). and the other at c2 = (1 d3/4 1, 1..... 1), along with many data points co-located at each center and one special point == (1,
Proof. The instance has two centers, one at the origin c1 = (0, 0, .
11, 1, 1). 1). We show that any distribution D over threshold trees (a single threshold cut in this case) yields an explainable clustering such that either the ε or the Eg cost is in expectation ((d2/1) times the corresponding unconstrained clustering cost.
Case I: If distribution D) assigns æ to with probability at least 1/2, then the expected & cost of the explainable clustering is at least d/2, while the optimal l clustering cost is d3/4 (by assigning x to c2).
Case 2: If distribution D assigns x to 02 with probability at least 1/2, the expected & cost of the explainable clustering is at least d3/4/2, while the optimal Eg clustering cost is vdd (by assigning x to c1).
D Lower bound for explainable k-medians under t, norm
In this section, we present a lower bound on the competitive ratio for the explainable k-medians problem under tp norm for all 2 1. In particular, we extend the lower bound instance for explainable k-medians clustering under & norm in Makarychev and Shan (2021) to lp norm for all p Z 1.
Theorem 4.1. For every p 2 1, there exists an instance X C Rd,, such that for every threshold tree T, its clustering cost is at least (X.t,(X.T) = 2ilog k) k)PPT (X), where OPT ) is the Ep cost of the optimal (unconstrained) k-medians clustering of X.
We construct the lower bound instance X as follows. Consider the grid G {0, e, 2e, 1]d that is obtained by discretizing the hypercube, where d = [64pp In and = 1/ ln We choose C, we place two data points Fa = c (c, (C.,,...,, c) and E22 = c (c,c,...,. c). Moreover, for every c E C. we place n data points Tej, j = 3,4, ... + that coincide with e (i.e. Æej c). We will show that the clustering instance X = U L j E [n + 2]} satisfies with positive probability two properties captured by Lemma D.1 and Lemma D.2 and then show that these properties suffice to prove Theorem 4.
A centers C' uniformly at random from the grid G and for each
The first property we show is that the with high probability all centers in the random set C' are well separated.
40

---

Lemma D.1. With probability at least 1 3, k2 for any two distinct centers d' E C. it holds that
d ||c - ---cllp- 12
Proof of Lemma D.I. An equivalent way choose center from the grid {0, c,,c,, 2c,,,..... 1]d random, to first choose E I- 1+ $1 uniformly at random and then choose c be the closest center of in the grid. Consider c, C. be distinct centers of the instance and let é and ě be their corresponding uniform random variables in
,,] uniformly
1-2, 1 + 2/ We have
d
2d(1 + E)
Ellle - 21
ElI - 217
(p +
where we used that for each coordinate i, & and 2 are independent uniform random variables in 3. 1 + L.. Moreover, the variables |& - 2 are independent for different i and are bounded in
[0, [1 + e) By Hoeffding's 's inequality, we have
Pr<11 | 21 (p + 1)(p+2) (1 +)* (2dddkk Pr
2d(1 + c)"
1
1-1
d(1+e)² thus Because d2 64pp* pz In k, we get that (1 c) 2d (p+1)(++2)
Pr Pr Pr |2
d(1 + E)P
}
1
(6)
(p + () + 2)
K
This means that with probability at least 1/k:
(1 e)d
| م|Ip 2 (p + 1) (p + 2)
Because e is the closest point in the grid 9 to č, then ||c - E||p S &d (the same holds for and 2¹). Thus, by the triangle inequality
(1 + c)a ||c 1c-cll22 (p (p+ ()+
dF 12"
cdt
The second inequality holds for sufficiently large k. since 1/ In k can be made arbitrarily small by increasing k, and because the function ((p + 2)) is decreasing for 2 1 and thus attains its maximum value at p = 1. By applying the union bound over all pairs of centers in C, the claim follows.
To describe the second property, we introduce some notation. Consider threshold tree and node u of this tree, Let F, C C' be the set of undamaged centers contained in u, i.e. the set of centers in the node such that all the points in the optimal cluster of are contained in the node u. We also define path sequence as any sequence of tuples (i1, 01), (12, 02, 02).... ... (it, 9r. J,), such that t 2 is an integer, i E [d]. fg E IR and Jr {+1). Note that any node is fully specified by the path from the root of 7 to u and thus by path sequence ग (u). where (1z, 02) is the j-th threshold cut in the path and a, indicates the direction of the next node in the path. Inversely, for given path sequence m we denote u(n (T) as the node that æ specifies, i.e.
u(T) = n EØER: ol.; - 0) 2 0}.
(1,0,0)ET
Lemma D.2. With probability at least L. for every 1 S logak
1 for every path sequence π
(6,, 01,01),..... (i....(i,00 (i, (1, with iz [d].0, 10,1),,, (#1}, one of the following holds:
1. the number of undamaged centers in u(T) is at most [FaGR) S Vk; or
2. any that separates centers in u(x) damages least e(Fugx)/22 centers in Fu(a)-
41

---

Proof of Lemma D.2. It suffices to prove the lemma for path sequences such that 8, E { Se
2. ......
{). This restriction is without loss of generality. since for every coordinate i [d] and for every r E {0, (0..,..., } all the cuts in the interval (re, (r + 1)e] are equivalent, in the sense that they induce the same partition of the grid points and thus of the instance X.
Fix any path sequence π of size t I logg h and denote u =u(T) for simplicity. Assume that the total number of undamaged centers in u is [F.. = k' > Vk. Given a threshold cut w = (1, 0), we define Zu to be the number of undamaged centers E F,, that are damaged by w. Conditioned on Fr = k', the undamaged centers contained u are distributed as k' points drawn independently and uniformly from the grid points G inside u, excluding the leftmost and rightmost grid points in each coordinate. Consider each undamaged center c E F Fu)). The new cut w damages this center c and only if c2 E {0 - e/2, 0 e/2]. Since there are at most 1/c possible grid positions for c, this undamaged center c is damaged by the cut w with probability at least c. Therefore, we have
7/ [u = K] 2 ek',
where the expectation is taken over the randomness of centers in F(u). Thus, by the Chernoff bound
Pr
{ 7 - "/ Full |uul= = k/ S Se- Se-
By taking the union bound over all possible cuts u (at most d/e = Og In² k) in total), we obtain some damages less than ck' /2 undamaged centers in F(u) with probability at most e 10 for sufficiently large k. Thus, the probability that both (1) and (2) do not hold is at most e -
Moreover, the number of different path sequences at fixed size is at most (22)² = Og In k)). Thus, by taking the union bound over all possible path sequences for every t S logg k the probability that both (a) and (b) do not hold is at most
logz k 2d
CVE 16 = (ing(r log k) kog.)) o// S
4
where the inequality holds for any fixed p when k is sufficiently large.
By Lemma D.I and D.2 there exists an instance X with centers and d = [64p' In ki such that both properties of these lemmas hold. Moreover, the optimal clustering has Lp cost OPTk.p 2ked as we can assign each data point Zej to center c. Consider any threshold tree T with & leaves. We will show that cost,p (X, T) = 2(log OPPT..p
First, we consider the case where T does not separate all centers in C, that is, there exists leaf of the tree that contains two centers and é'. Note that there are n data points located at each of the centers e and c'. Hence, the cost of this leaf is least n n/|lc c' c/I1p/2 2 nd /24 by Lemma D. This
cost can be arbitrarily large since n can be arbitrarily large.
Next, consider the threshold tree TT in which each leaf contains exactly one center from C. We divide it into the following two cases. In the first case, suppose there exists level S I
loga & that 4
contains at least & damaged centers. For each damaged center, there is a data point that was assigned to it in the optimal solution but is reassigned to another center by TT Each such reassignment incurs cost of ((d-/P). Thus, the total cost of T is at least 2 ( d(/) 22log k)OPTk,, since = =1/1n In k.
k the number of undamaged centers level t In the second case, assume that for every 1 < ".
of T is at most k We call node small if it contains at most v/k undamaged centers, and large otherwise. Fix any in 21. log, }. Since the total number of nodes at level is at most 1 4
the small nodes together contain at most & undamaged centers. Hence, the large nodes contain at least & - k > undamaged centers for sufficiently large k. Because 'T contains exactly one center 3
from C, all thresholds of cuts lie within [0, 1]. By Lemma D.2, the number of undamaged centers that become damaged at level of T is at least ck Since each damaged center incurs a reassignment cost of (P) by Lemma D.I, the total cost at level t is (/ek By summing over all levels the total cost is 4-
1 < 1 < Jog, d.
Ω (Log k ekdž) 2(log O
42


Reviews:
[{"review_id": "mhKmrO9HHW", "reviewer": "Reviewer_auTj", "summary": "This paper addresses the problem of maintaining an explainable clustering under dynamic updates, specifically a decision tree clustering that approximates the $k$-medians objective. The goal is to construct and maintain a tree structure that enables interpretable clustering while achieving provable approximation guarantees. The authors present an algorithm that achieves an approximation factor of $O(p \\log^{1 + 1/p - 1/p^2} k \\log \\log k)$ for the $k$-medians problem under the $\\ell_p$ norm. Prior to this work, such guarantees were only known for the $\\ell_1$ norm ($p = 1$), and for $p = 2$ (Euclidean case), the best-known explainable clustering algorithm had a weaker approximation factor of $O(\\log^{3/2} k)$. A lower bound of $O(\\log k)$ was already known. In addition to extending explainable clustering to general $\\ell_p$ metrics, the authors also design a dynamic algorithm that maintains the same approximation factor under insertions and deletions.", "questions": "-", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The $k$-median problem is both important and widely applicable, and designing a data structure that supports fast updates while maintaining clustering quality is a meaningful direction. While most practical applications involve $p = 1, 2$, extending the results to general $\\ell_p$ norms is also of theoretical interest. Although the paper builds on several ideas from Makarychev and Shan (2021), the results are nontrivial and contribute meaningfully to the area, making the paper a reasonable candidate for acceptance.", "was_revised": true, "final_justification": "The results are solid and justify acceptance.", "rebuttal": "We thank the reviewer for the detailed and insightful comments."}, {"review_id": "YqQf8J4Cb7", "reviewer": "Reviewer_X4Dr", "summary": "The authors introduce an algorithm for explainable $k$-medians clustering problem under $\\ell_p$ norm for generic $p \\geq 1$. The authors also prove its approximation results, which were not known before. The author also discuss how this algorithm could be extended to dynamic settings.", "questions": "* Can the authors comment about the technical intuitions when extending the results from $p = 1,2$ to $p \\geq 1$?\n* Including a brief mention of hardness results in the introductory section would be appreciated, personally.", "limitations": "The paper does not include a paragraph addressing their limitations as it is a theory paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n* I highly appreciate the technical contributions and the elegance of the proofs presented in this paper.\n* The authors also include a dynamic version of their algorithm to enhance their approach.\n\nWeaknesses\n* Practical discussions or experiments are not present; understandable as this is a theory paper.\n* (minor point) In line 916 and 988, Hölder's ineqaulity should be used.", "was_revised": true, "final_justification": "Solid results and should be accepted.", "rebuttal": "We thank the reviewer for the detailed and constructive feedback. \n\n1. The main intuition of extending the results from $p=1,2$ to general $p>=1$ is as follows. We build on the algorithmic framework of Makarychev and Shan (2021) for explainable k-medians under $\\ell_2$ norm. The key modification lies in the sampling distribution for the threshold $\\theta \\in [0,R_t]$ in the Partition_Leaf function. Specifically, we sample theta according to the cumulative density function $x^p/(R_t)^p$, which corresponds to the density function $px^{p-1}/(R_t)^p$. This implies that for any $0<a<b<R_t$, the probability that the sampled threshold $\\theta \\in [a,b]$ is at most $p(b-a)b^p/(R_t)^p$, which is crucial for bounding the separation probability.  Our analysis is more refined than that of Makarychev and Shan (2021); as a result, it applies to all finite $p$ and yields improved theoretical guarantees for the $\\ell_2$ norm. \n\nNote that these modifications are necessary to achieve a good approximation for $p \\geq 1$. Specifically, for every value of $p$ we need to use a separate distribution. This is illustrated by the example we provide in our response to Reviewer tdu1 (see our answer to Q1 for Reviewer tdu1).\n\n\n2. We have an example that shows an $\\Omega(\\log k)$ lower bound on the price of explainability for $k$‑medians under the $\\ell_p$ norm for all $p \\geq 1$. We will include it in the revised version of the paper. We will also expand the discussion of related lower bounds and hardness of approximation results, including the $\\Omega(\\log k)$ lower bound on the price of explainability for $k$‑medians under the $\\ell_2$ norm due to Makarychev and Shan (2021) and the hardness results for explainable $k$‑medians under the $\\ell_1$ norm by Gupta, Pittu, Svensson, and Yuan (2023)."}, {"review_id": "LtofxwjGfX", "reviewer": "Reviewer_ZVnr", "summary": "This paper presents results for the explainable $k$-median problem for $\\ell_p$ norm distance. The improve the state of the art for the case of $k$-means. The authors also extend their results to dynamic settings.", "questions": "What are the differences between the dynamic settings in this paper and the previous works?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The paper is well written and the ideas and techniques are explained clearly.\n\n- The setting is interesting; although explainable algorithms provide lower quality clustering, they are interpretable and each decision on the tree depends on a single feature. In many real world applications, these are key constraints.\n\n- The results are strong: i) The improvements for $\\ell = 2$ is interesting, ii) For the higher values, this works presents the first result.\n\n- The results in the dynamic setting are interesting but not as interesting as the offline setting. The setting seems to be different from multiple other k-median clustering problems in a dynamic setting. In most settings the points are inserted / deleted but in this work the centers are changing.", "was_revised": true, "final_justification": "Good paper with solid contribution.", "rebuttal": "We thank the reviewer for the detailed comments and appreciate the recognition of our results in the offline setting.\n\nWe are not aware of any prior work on dynamic algorithms for explainable clustering. Dynamic algorithms have, however, been studied for unconstrained (non-explainable) $k$‑medians. While our dynamic algorithm is stated in terms of insertions and deletions of centers, it can be naturally combined with existing dynamic algorithms for unconstrained k-medians under $\\ell_p$ norm to also handle dynamic updates to the data points themselves. Specifically, in settings where data points are inserted or deleted, we can maintain a good set of centers using a dynamic $k$-medians algorithm, and then use our algorithm to maintain the corresponding threshold tree for explainable clustering as these centers change. In particular, we can use a constant-factor approximation dynamic algorithm with small recourse that modifies only a small number of centers upon each insertion or deletion of a data point. We will include a clear discussion of this connection and state a formal corollary in the revised version."}, {"review_id": "UVBtdZ3Cqw", "reviewer": "Reviewer_3zna", "summary": "Explainable clustering seeks to partition a set of points into clusters, where the cluster boundaries are given by coordinate cuts. One key question is how far the quality of clustering is with respect to an optimal clustering (which need not obey such restrictions on cluster boundaries). For the $k$-median objective, it is known that one can obtain $O(\\log k)$-approximate explainable clustering and it is tight. The paper considers a more general objective where one needs to open $k$ centers (as in the $k$-median case), but the cost of assigning a client $x$ to a center $y$ is given by $||x-y||_p$ ($\\ell_p$ norm). When $p=2$, $O(\\log^{1.5} k)$-approximation algorithm was known (ignoring loglog factors). There are several results in the paper: \n\n1. For the general $p$ norm objective, they give $O(p (\\log k)^{1+1/p-1/p^2}$ approximation -- this improves the result for $p=2$ to $O(log^{1.25} k)$-approximation. \n2. They show that the algorithm can be implemented in a dynamic setting where points are arriving online and the update time is $O(k polylog(n))$.", "questions": "1. Clearly distinguish the main itechnical deas from the [Makarychev and Shan (2021)] paper: in particular, is the new contribution the distribution with which to choose $\\theta_t$ values? \n2. In the dynamic setting, what are the new ideas...it seems the core algorithm for explainable clustering remains similar to prior work...so would the ideas for dynamic setting also extend to prior works? \n3. What is the utility of these metrics in the context of explainable clustering?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. Improved bounds for $p = 2$, and new algorithms for general $p$\n2. The fact that these algorithms can be implemented in a dynamic setting is useful. \n3. The problem has received lot of attention in the recent past, specially in the context of explainable AI\n4. The techniques, though relying on prior work, still need fair bit of work for general $p$. \n\nWeakness: \n1. The template of the algorithm is very similar to prior work [Makarychev and Shan (2021)]\n2. In general $p=1$ and $p=2$ are the most useful settings (and the $k$-means objective). So it is not clear how useful these results are. \n3. An experimental validation showing that general $p$ matter in this context would have been useful.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback. \n\n1. As the reviewer correctly points out, our algorithm generalizes the one in Makarychev and Shan (2021), with the key difference being the modified distribution used to sample the threshold $\\theta$. This change is essential for extending the guarantees to general $\\ell_p$ norms. Beyond this algorithmic modification, our analysis introduces several new technical components. To achieve a tighter approximation ratio, we refine the analysis by partitioning cuts into three cases: (1) safe cut, (2) light cut, and (3) heavy and unsafe cut, while the previous work only considered light and heavy cuts. Additionally, the dynamic setting in this paper is entirely new. We will clarify these distinctions more explicitly in the revised version.\n\n2. We thank the reviewer for the insightful comment and agree that the core algorithm for explainable clustering remains similar to prior work. The reviewer is also correct that the new ideas introduced for the dynamic setting can be extended to earlier algorithms for explainable k-medians under both the $\\ell_1$ and $\\ell_2$​ norms. \nWhile the high-level structure of the algorithm is preserved, the dynamic setting introduces several new technical challenges that require novel ideas:\n\n(1) We use exponential clocks to assign timestamps to decision nodes, allowing us to identify the earliest cut that separates an inserted center and update the threshold tree. This avoids recomputing the entire tree from scratch. Specifically, the exponential timestamps allow us to update the current tree efficiently in time O(d polylog k). Note that even classifying a single data point $x$ naively might require traversing a root-to-leaf path in O(k) time. Although exponential clocks were previously used in the analysis of $\\ell_1$-based clustering algorithms (e.g., Gupta et al. 2023; Makarychev and Shan 2023), this is the first time they are used algorithmically for maintaining the dynamic explainable clustering.\n\n(2) Our static algorithm selects the anchor point as the coordinate-wise median of centers to control the number of centers separated by each cut. In the dynamic setting, the median of centers evolves as centers are inserted or deleted, which implicitly affects the threshold distribution. To address this, we keep track of the number of centers and rebuild the tree when necessary to maintain the anchor point as an approximate median of centers in each partition leaf call.\n\n3. We thank the reviewer for the thoughtful question. Studying $\\ell_p$ norm costs in clustering provides a flexible framework that interpolates between different clustering objectives, with practical and theoretical relevance. For instance, $\\ell_1$ norm is known for its robustness to outliers, while $\\ell_2$ norm is widely used due to its geometric interpretability and computational properties. Extending explainable clustering to general $\\ell_p$​ norms allows practitioners to tailor the cost function to the needs of specific applications while preserving interpretability. Our goal is to understand how explainability impacts clustering quality across this broader family of objectives and to provide provable guarantees in this more general setting."}, {"review_id": "qKCOWphaCq", "reviewer": "Reviewer_tdu1", "summary": "This paper studies the problem of constructing a threshold decision tree that partitions data into k clusters while minimizing the k-median objective under the l_p  norm. Unlike the classical k-median problem, where each node is assigned to the nearest center based on distance, this approach assigns nodes based on decision rules within a tree structure. Each internal node compares a feature value to a threshold and directs the data point to either the left or right subtree, continuing recursively until it reaches a leaf node, which represents a cluster. This tree-based clustering method enhances interpretability by making the clustering structure more transparent and easier to understand.\nThe authors propose an algorithm with an approximation ratio of O(p⋅log^{1+1/p −1/p^2} k⋅log log k) under the l_p norm for all p≥1, improving upon existing bounds for p=2. Additionally, the paper extends the approach to dynamic clustering, supporting both insertions and deletions of nodes. The dynamic algorithm maintains the same approximation ratio, with an amortized update time (i.e., threshold changes) of O(d log^3 k) and an amortized recourse (i.e., the number of nodes changes to the tree structure) of O(log k).", "questions": "I am curious about the explainable clustering problem in the setting where the centers are given as part of the input. Is it possible to construct a single clustering tree that performs well across all l_p norms, rather than building a separate explainable tree for each specific norm? Why or why not?\n\nAdditionally, regarding the dynamic clustering algorithm, normalization is applied to all centers. Will normalization also need to be applied to all nodes whenever new nodes are inserted? If so, how does this affect the efficiency of the algorithm?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe explainable clustering problem is both important and interesting. The authors extend the algorithm to handle the l_p norm and improve upon the best-known approximation ratio for p=2. The techniques and analysis are solid and well-justified. The extension to the dynamic setting is also a valuable contribution—particularly in low-dimensional spaces, where the results are especially strong and practical. I have not read the entire proof in detail, but it appears to be logically sound. \n\nWeaknesses: \nThe authors do not discuss lower bounds in detail, nor do they attempt to establish any lower bounds for the l_p norms in either the static or dynamic settings.\n\nSmall comments:\nLine 140: O(p⋅log^{1+1/p −1/p^2} ⋅log log k) -> O(p⋅log^{1+1/p −1/p^2} k⋅log log k), miss k. \nLine 191: m_i^u ->  m_{i_t}^u", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments and insightful questions. \n\nW1: We have an example that shows an $\\Omega(\\log k)$ lower bound on the price of explainability for $k$‑medians under the $\\ell_p$ norm for all $p \\geq 1$. We will include it in the revised version of the paper. We will also expand the discussion of related lower bounds and hardness of approximation results, including the $\\Omega(\\log k)$ lower bound on the price of explainability for $k$‑medians under the $\\ell_2$ norm due to Makarychev and Shan (2021) and the hardness results for explainable $k$‑medians under the $\\ell_1$ norm by Gupta, Pittu, Svensson, and Yuan (2023).\n\nQ1. I am curious about the explainable clustering problem in the setting where the centers are given as part of the input. Is it possible to construct a single clustering tree that performs well across all l_p norms, rather than building a separate explainable tree for each specific norm? Why or why not?\n\nThank you for the excellent question! There exists an instance with two centers such that no single threshold tree (even distribution over threshold trees) can achieve better than O(d^{1/4}) approximation for all $\\ell_p$ norms simultaneously. We will include this example in the revised version. \n\nThe instance has two centers, one at the origin $c_1=(0,0,\\dots,0)$, and the other at $c_2=(1 + d^{\\frac{3}{4}},1,\\dots,1)$, along with many data points co-located at each center and one special point $x = (1,1,\\dots, 1)$. We show that any distribution $D$ over threshold trees (a single threshold cut in this case) yields an explainable clustering such that either the $\\ell_1$ or the $\\ell_2$ cost is in expectation $\\Omega(d^{\\frac{1}{4}})$ times the corresponding unconstrained clustering cost.\n\nCase 1: If distribution $D$ assigns $x$ to $c_1$ with probability at least $1/2$, then the expected $\\ell_1$ cost of the explainable clustering is at least $d/2$, while the optimal $\\ell_1$ clustering cost is $d^{3/4}$ (by assigning $x$ to $c_2$). \n\nCase 2: If distribution $D$ assigns $x$ to $c_2$ with probability at least $1/2$, the expected $\\ell_2$ cost of the explainable clustering is at least $d^{3/4}/2$, while the optimal $\\ell_2$ clustering cost is $\\sqrt{d}$ (by assigning $x$ to $c_1$).  \n\nQ2. Additionally, regarding the dynamic clustering algorithm, normalization is applied to all centers. Will normalization also need to be applied to all nodes whenever new nodes are inserted? If so, how does this affect the efficiency of the algorithm?\n\nAs far as your second question is concerned, the assumption that all future centers lie in $[-1,1]^d$ is used mainly for the ease of exposition. There is an implementation of the algorithm that does not depend on this assumption. Specifically, if the centers after request $t$ lie in $[-R,R]^d$, the weighted distribution $\\tilde{f}(x)$ that we use to sample a threshold in $(y_{j-1}, y]$ does not depend on $R$ (we can compute the threshold by sampling a uniform random variable $U \\in ((y_{j-1} - m)^p, (y-m)^p)$ and return $U^{1/p}$). Moreover, if all timestamps are multiplied by the same positive number $\\alpha$, the analysis is not affected. Thus, in line 1171, we can sample $z\\sim \\exp(\\lambda)$ with $\\lambda = (y-m)^p - (y_{j-1} - m)^p$ (that does not depend on R), without affecting the analysis. We will add this clarification in the revised version of the paper."}]

Author rebuttal:

Meta-review: This paper studies explainable clustering in metric spaces under dynamic updates, the papers improves previous work on \ell_2 for the same problem and generalize to other \ell_p.

The studied problem is natural and of practical interest and the techniques in the paper generalize previous work. The paper would benefit from experiments and from a more detail comparison with Makarychev and Shan (2021) but overall it is above the acceptance bar.
Decision: Accept (spotlight)