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. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru