1972/09/01 by D. Jack Elzinga, Donald W. Hearn · 184 citations
Business, Management and Accounting · Computer Science · Mathematics · #Facility Location and Emergency Management #Computational Geometry and Mesh Generation #Advanced Optimization Algorithms Research #Simplex #Mathematics #Quadratic programming #Converse #Finite set #Duality (order theory) #Linear programming #Quadratic equation #Simplex algorithm #Mathematical optimization #Set (abstract data type) #Combinatorics #Computer science #Mathematical analysis #Geometry
paper · doi:10.1287/mnsc.19.1.96
published in Management Science 19(1), 96-104 (Institute for Operations Research and the Management Sciences)
openalex publication_date 1972/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.