RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2013, Volume 20, Number 1, Pages 93–99 (Mi da721)  

This article is cited in 1 scientific paper (total in 1 paper)

The smallest $k$-enclosing ball problem

V. V. Shenmaier

Sobolev Institute of Mathematics, Novosibirsk, Russia

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.

Full text: PDF file (237 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 444–448

Bibliographic databases:

UDC: 519.176
Received: 26.07.2012

Citation: V. V. Shenmaier, “The smallest $k$-enclosing ball problem”, Diskretn. Anal. Issled. Oper., 20:1 (2013), 93–99; J. Appl. Industr. Math., 7:3 (2013), 444–448

Citation in format AMSBIB
\Bibitem{She13}
\by V.~V.~Shenmaier
\paper The smallest $k$-enclosing ball problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2013
\vol 20
\issue 1
\pages 93--99
\mathnet{http://mi.mathnet.ru/da721}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3088151}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 3
\pages 444--448
\crossref{https://doi.org/10.1134/S1990478913030186}


Linking options:
  • http://mi.mathnet.ru/eng/da721
  • http://mi.mathnet.ru/eng/da/v20/i1/p93

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Sh. I. Galiev, A. V. Khorkov, “Mnogokratnye pokrytiya krugami ravnostoronnego treugolnika, kvadrata i kruga”, Diskretn. analiz i issled. oper., 22:6 (2015), 5–28  mathnet  crossref  mathscinet  elib
  • ƒискретный анализ и исследование операций
    Number of views:
    This page:264
    Full text:79
    References:33
    First page:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020