Institute of Mathematics & Computer Science, Hebrew University, Jerusalem, Israel and Electrical Engineering & Computer Science & Mathematics Departments, University of Michigan, Ann Arbor, Michigan 48109
Institute of Mathematics & Computer Science, Hebrew University, Jerusalem, Israel and Electrical Engineering & Computer Science & Mathematics Departments, University of Michigan, Ann Arbor, Michigan 48109
We show that the complexity of the Elzinga-Hearn algorithm for the 1-center (single facility minimax) problem is Ω(n2). We also show that the algorithm reaches a solution within any given accuracy in O(n) time.
Zvi Drezner, Saharon Shelah, (1987) On the Complexity of the Elzinga-Hearn Algorithm for the 1-Center Problem. Mathematics of Operations Research 12(2):255-261.
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.