A faster dual algorithm for the Euclidean minimum covering ball problem

Marta Cavaleiro, Farid Alizadeh

Research output: Contribution to journalArticle


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.

Original languageEnglish (US)
JournalAnnals of Operations Research
StateAccepted/In press - Jan 1 2020


All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research


  • 1-Center
  • Computational geometry
  • Minimum covering ball
  • Minmax location
  • Smallest enclosing ball

Cite this