Задача о минимальном шаре, охватывающем $k$ точек

Рассматривается задача поиска шара минимального радиуса, охватывающего не менее $k$ точек из заданного конечного множества в евклидовом пространстве. В случае фиксированной размерности пространства задача полиномиально разрешима, но в общем случае сложностной статус задачи до настоящего времени не был установлен. Доказано, что задача NP-трудна в сильном смысле, а также получена полиномиальная аппроксимационная схема (PTAS), позволяющая решать задачу с произвольной относительной погрешностью $\varepsilon$ за время $O(n^{1/\varepsilon^2+1}d)$, где $n$ – мощность исходного множества, $d$ – размерность пространства. Библиогр. 10.