For a metric space $(X,d)$, given $N$ points $S=(s_1,\dotsc,s_N) \subset X^N$, a $k$-median is a multiset of centers $K=\{c_1,\dotsc,c_k\} \subset X$, $k\leq N$, that minimizes $$ f_S(K) \equiv \sum_{n=1}^Nd(s_n,K) = \sum_{n=1}^N \min_{1\leq j\leq k}d(s_n,c_j). $$
$1$-medians aren't necessarily unique, so $k$-medians definitely aren't, so I'm instead interested in upperbounds on how "far" the $k$-medians can be away from each other. More concretely I'm seeking non-trivial (possibly tight) bounds on $$\sup_{K_1,K_2\in \operatorname{Argmin}_K f_S(K)} d(K_1,K_2),$$ where $d(K_1,K_2)$ is the cost of the minimum bipartite matching between the multisets (i.e., $d(K_1,K_2) = \min_{\sigma \in \Pi^k} \sum_{j=1}^k d(c^1_j,c^2_{\sigma_j})$, where $\Pi^k$ denotes the symmetric group of order $k$).
I'd be interested in results for the special case of $(X,d) = (\mathbb{R}^D, \|\cdot\|_2)$ too.