EN|RU Volume 20, No 1, 2013, P. 93-99 UDC 519.176 Shenmaier V. V.  The smallest k-enclosing ball problem Abstract: The smallest $k$-enclosing ball problem is considered: given a finite set of points in the Euclidean space and an integer $k$, find the smallest circle containing at least $k$ of the points. If the space dimension is fixed, the problem is polynomial-time solvable. In the general case, when the dimension belongs to the data input, the complexity status of the problem is still unknown. Strong NP-hardness of the problem is proved and an approximation scheme (PTAS) that solves this problem with an arbitrary relative error $\varepsilon$ in time $O(n^{1/\varepsilon^2+1}d)$, where $n$ is the number of points in the origin set and $d$ is the space dimension, is presented. Bibliogr. 10. Keywords: smallest enclosing ball, k-enclosing ball, cluster analysis, approximation scheme, approximation algorithm. Shenmaier Vladimir Vladimirovich 1 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia e-mail: shenmaier@mail.ru © Sobolev Institute of Mathematics, 2015