Before revision:  We extend these results by showing that also the k-median problem is NP-hard for k=1.
After revision:  We extend these results by showing that also the k-median problem is NP-hard .