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 n . 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.

• 저널Management Science · 19(1) · 96–104
• 토픽Facility Location and Emergency Management · Organizational Behavior and Human Resource Management
• DOI10.1287/mnsc.19.1.96
• 저자D. Jack Elzinga, Donald W. Hearn