The Minimum Covering Sphere Problem

The minimum covering sphere problem, with applications in location theory, is that of finding the sphere of smallest radius which encloses a set of points in Eⁿ. For a finite set of points, it is shown that the Wolfe dual is equivalent to a particular quadratic programming problem and that converse duality holds. A finite decomposition algorithm, based on the Simplex method of quadratic programming, is developed for which computer storage requirements are independent of the number of points and computing time is approximately linear in the number of points.