## 4 \(k\)-Means++ for \(\rho\)-Metric  
In this section we suggest a generalization of the \(k\)-means++ algorithm for every \(\rho\)-metric and not only distance to the power of \(z\geq 1\) as claimed in the original version. In particular, we consider nonconvex \(M\)-estimator functions. Our goal is then to compute an \(\alpha\)-approximation to the \(k\)-median problem for \(\alpha=O(\log k)\). Let \(w:P\to(0,\infty)\) be called the _weight function_ over \(P\). For a nonempty set \(Q\subseteq P\) we define  
\[f(Q,X)=f_{w}(Q,X)=\sum_{p\in Q}w(p)f(p,X).\]  
If \(Q\) is empty then \(f(Q,X)=0\). For brevity, we denote \(f(Q,p)=f(Q,\{p\})\), and \(f^{2}(\cdot)=(f(\cdot))^{2}\). For an integer \(k\geq 1\) we denote \([k]=\{1,\cdots,k\}\). **Definition 3** (\(k\)-median for \(\rho\)-metric spaces). : _Let \((P,f)\) be a \(\rho\)-metric, and \(k\in[n]\) be an integer. A set \(X^{*}\subseteq P\) is a \(k\)-median of \(P\) if_  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]  
_and this optimum is denoted by \(f^{*}(P,k):=f(P,X^{*})\). For \(\alpha\geq 0\), a set \(Y\subseteq P\) is an \(\alpha\)-approximation for the \(k\)-median of \(P\) if_  
\[f(P,X^{*})\leq\alpha f^{*}(P,k).\]  
_Note that \(Y\) might have less or more than \(k\) centers._  
The following lemma implies that sampling an input point, based on the distribution of \(w\), gives a \(2\)-approximation to the \(1\)-mean. **Lemma 5**. : _For every nonempty set \(Q\subseteq P\),_  
\[\sum_{x\in Q}w(x)f_{w}(Q,x)\leq 2\rho f_{w}^{*}(Q,1)\sum_{x\in Q}w(x). \tag{22}\]  
Proof. : Let \(p^{*}\) be the weighted median of \(Q\), i.e., \(f_{w}(Q,p^{*})=f_{w}^{*}(Q,1)\). By (1), for every \(q,x\in Q\),  
\[f(q,x)\leq\rho\big{(}f(q,p^{*})+f(p^{*},x)\big{)}.\]  
Summing over every weighted \(q\in Q\) yields  
\[f_{w}(Q,x)\leq\rho\big{(}f_{w}(Q,p^{*})+f(p^{*},x)\sum_{q\in Q}w(q)\big{)}= \rho\big{(}f_{w}^{*}(Q,1)+f(x,p^{*})\sum_{q\in Q}w(q)\big{)}.\]  
Summing again over the weighted points of \(Q\) yields  
\[\sum_{x\in Q}w(x)f_{w}(Q,x)\leq\rho\sum_{x\in Q}w(x)\big{(}f_{w}^{*}(Q,1)+f(x,p^{*})\sum_{q\in Q}w(q)\big{)}=2\rho f_{w}^{*}(Q,1)\sum_{x\in Q}w(x).\]  
We also need the following approximated triangle inequality for weighted sets. **Corollary 1** (Approximated triangle inequality). : _Let \(x\in P\), and \(Q,X\subseteq P\) be nonempty sets. Then_  
\[f(x,X)\sum_{q\in Q}w(q)\leq\rho(f_{w}(Q,x)+f_{w}(Q,X)).\]  
**Proof. ** Summing (2) over every weighted \(q\in Q\) yields  
\[f(x,X)\sum_{q\in Q}w(q) \leq\rho\left(\sum_{q\in Q}w(q)f(q,x)+\sum_{q\in Q}w(q)f(q,X)\right)\] \[=\rho(f_{w}(Q,x)+f_{w}(Q,X)).\]  
The following lemma states that if we use sampling from \(P\) and hit a point in an uncovered cluster \(Q\), then it is a 2-approximation for \(f^{*}(P,1)\). **Lemma 6**. : _Let \(Q,X\subseteq P\) such that \(f_{w}(Q,X)>0\). Then_  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]0  
**Proof. ** By Corollary 1, for every \(x\in Q\),  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]1  
Multiplying this by \(\frac{f_{w}(Q,X\cup\{x\})}{f_{w}(Q,X)}\) yields  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]2 \[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]3  
After summing over every weighted point \(x\in Q\) we obtain  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]4  
Finally, this lemma is the generalization of the original lemma of the \(k\)-means++ versions. **Lemma 7**. : _Let \(t,u\geq 0\) be a pair of integers. If \(u\in[k]\) and \(t\in\{0,\cdots,u\}\) then the following holds._  
_Let \(\{P_{1},\cdots,P_{k}\}\) be a partition of \(P\) such that \(\sum_{i=1}^{k}f^{*}(P_{i},1)=f^{*}(P,k)\). Let \(U=\bigcup_{i=1}^{u}P_{i}\) denote the union of the first \(u\) sets. Let \(X\subseteq P\) be a set that covers \(P\setminus U\), i.e., \(X\cap P_{i}\
eq\emptyset\) for every integer \(i\in[k]\setminus[u]\), and \(X\cap U=\emptyset\). Let \(Y\) be the output of a call to KMeans++\((P,w,f,X,t)\); see Algorithm 1. Then_  
\[f(P,X^{*})=\min_{X\subseteq P,|X|=k}f(P,X),\]5  
_where \(H_{t}= \begin{cases}\sum_{i=1}^{t}\frac{1}{t}&\text{if }t\geq 1\\ 1&\text{if }t=0\end{cases}