k-Median Clustering

Say we have $n$ points $x_1,x_2,\dots ,x_n$. We want to partition them into $k$ sets $S_1,S_2,\dots ,S_k$ such that the cost of the partition is minimised, $c(S_1,S_2,\dots ,S_k)$:

$$c(S_1,S_2,\dots ,S_k)=\sum _{i=1}^n\underset{j\in [k]}{\min }\left[\begin{array}{c}||x_i-{\mu }_j|{|}_1\end{array}\right]$$

Where ${\mu }_i$ is the mid-point of each cluster, i.e. ${\mu }_i=\frac{1}{|S_i|}{\sum }_{j\in S_i}{x}_j$. Where $||\cdot |{|}_1$ is the L1 norm (Manhattan distance).