Dearing and Zeck (Oper Res Lett 37(3):171–175, 2009) presented a dual algorithm for the problem of the minimum covering ball in Rn. Each iteration of their algorithm has a computational complexity of at least O(n3). In this paper we propose a modification to their algorithm that, together with an implementation that uses updates to the QR factorization of a suitable matrix, achieves a O(n2) iteration.
All Science Journal Classification (ASJC) codes
- Decision Sciences(all)
- Management Science and Operations Research
- Computational geometry
- Minimum covering ball
- Minmax location
- Smallest enclosing ball