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/

[1] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskret. analiz i issled. operatsii, 17:5 (2010), 37–45 | MR

[2] Aggarwal A., Imai H., Katoh N., Suri S., “Finding $k$ points with minimum diameter and related problems”, J. Algorithms, 12 (1991), 38–56 | DOI | MR | Zbl

[3] Badoiu M., Clarkson K. L., “Smaller core-sets for balls”, Proc. 14th ACM-SIAM Symposium on Discrete Alg. (Baltimore, January 12–14, 2003), SIAM, Philadelphia, 2003, 801–802 | MR | Zbl

[4] Eppstein D., Erickson J., “Iterated nearest neighbors and finding minimal polytopes”, Discrete Comput. Geom., 11 (1994), 321–350 | DOI | MR | Zbl

[5] Garey M. R., Johnson D. S., “ ‘Strong’ NP-completeness results: motivation, examples, and implications \”, J. ACM, 25:3 (1978), 499–508 | DOI | MR | Zbl

[6] Har-Peled S., Mazumdar S., “Fast algorithms for computing the smallest $k$-enclosing disc”, Algorithmica, 41:3 (2005), 147–157 | DOI | MR | Zbl

[7] Papadimitriou C. H., Computational complexity, Addison-Wesley, New York, 1994, 523 pp. | MR | Zbl

[8] Sylvester J. J., “A question in the geometry of situation”, Quart. J. Math., 1 (1857), 79

[9] Vazirani V., Approximation algorithms, Springer-Verl., Berlin, 2001, 71 pp. | MR

[10] Wirth H., Algorithms+data structures=programs, Prentice Hall, New Jersey, 1976, 366 pp. | MR | Zbl