Geodesic
The smallest $k$-enclosing ball problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 93-99

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2013_20_1_a7,
     author = {V. V. Shenmaier},
     title = {The smallest $k$-enclosing ball problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {93--99},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - The smallest $k$-enclosing ball problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 93
EP  - 99
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/
LA  - ru
ID  - DA_2013_20_1_a7
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T The smallest $k$-enclosing ball problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 93-99
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/
%G ru
%F DA_2013_20_1_a7
V. V. Shenmaier. The smallest $k$-enclosing ball problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 93-99. http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/