Before revision:  The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball under the Fr\'echet distance . We extend these results by showing that also the k-median problem is NP-hard for k=1.
After revision:  The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball under the Fr\'echet distance , we show that also the k-median problem is NP-hard for k=1.