Complexity and approximation of the smallest k-enclosing ball problem
Vladimir Shenmaier · Scuola Normale Superiore eBooks · 2013
Given an n -point set in Euclidean space ℝ d and an integer k , consider the problem of finding the smallest ball enclosing at least k of the points. In the case of a fixed dimension the problem is polynomial-time solvable but in the general case, when d is not fixed, the complexity status of the problem was not yet known. We prove that the problem is strongly NP-hard and describe an idea of PTAS. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.