Efficient Algorithms for the (Weighted) Minimum Circle Problem

1982/08/01 by Donald W. Hearn, James Vijay · 116 citations
Business, Management and Accounting · Mathematics · #Facility Location and Emergency Management #Scheme (mathematics) #Algorithm #Computer science #Facility location problem #Mathematics #Mathematical optimization

paper · doi:10.1287/opre.30.4.777

published in Operations Research 30(4), 777-795 (Institute for Operations Research and the Management Sciences)

openalex publication_date 1982/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

The (weighted) minimum covering circle problem is a well-known single facility location problem used in emergency facility models. This paper introduces a classification scheme, based on fundamental mathematical programming concepts, for algorithms which solve both weighted and unweighted versions. One result of this classification is proof that a recently developed method is identical to one developed in the nineteenth century. Also, within the classification scheme, efficient new algorithms are given for the weighted problem. The results of some extensive computational tests identify the (empirically) fastest methods.

Citations

• An algorithm for the minimax weber problem
• Minimax Multifacility Location with Euclidean Distances
• Geometrical Solutions for Some Minimax Location Problems
• Letter to the Editor—Note on Geometrical Solution for Some Minimax Location Problems
• The Minimum Covering Sphere Problem

Cited by

• On the Complexity of the Elzinga-Hearn Algorithm for the 1-Center Problem
• Smallest-circle problem [wikipedia]