k-clustering problems
The problem of minimizing the sum of distances from points to cluster centers is called the $k$-median problem. In a general metric space, the $k$-median can be approximated to within a factor of $3+\epsilon$ and is $\mathsf{MAX SNP}$-hard. In Euclidean space, the problem admits a PTAS. This is a good survey and has references for the above facts.