  In the Geometric Median problem with outliers, we are given a finite set of
points in d-dimensional real space and an integer m, the goal is to locate a
new point in space (center) and choose m of the input points to minimize the
sum of the Euclidean distances from the center to the chosen points. This
problem can be solved "almost exactly" in polynomial time if d is fixed and
admits an approximation scheme PTAS in high dimensions. However, the complexity
of the problem was an open question. We prove that, if the dimension of space
is not fixed, Geometric Median with outliers is strongly NP-hard, does not
admit approximation schemes FPTAS unless P=NP, and is W[1]-hard with respect to
the parameter m. The proof is done by a reduction from the Independent Set
problem. Based on a similar reduction, we also get the NP-hardness of closely
related geometric 2-clustering problems in which it is required to partition a
given set of points into two balanced clusters minimizing the cost of median
clustering. Finally, we study Geometric Median with outliers in $\ell_\infty$
space and prove the same complexity results as for the Euclidean problem.
