Given an n -point set in a d -dimensional space and an integer k , consider the problem of finding a smallest ball enclosing at least k of the points. In the case of a fixed dimension, the problem is polynomial-time solvable but in general, when d is not fixed, the complexity status is not known. We prove the strong NP -hardness in the case of Euclidean space and the ( 2 - e ) -inapproximability in the case of L ∞ metric. We also present a simple 2-approximation algorithm for any metric, and PTAS for L ∞ -space of dimension O ( log n ) .
['V. V. Shenmaier']
Complexity and approximation of the Smallest k -Enclosing Ball problem