A faster dual algorithm for the Euclidean minimum covering ball problem

Marta Cavaleiro, Farid Alizadeh

Research output: Contribution to journalArticle

Abstract

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
DOIs
StateAccepted/In press - Jan 1 2020

    Fingerprint

All Science Journal Classification (ASJC) codes

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

Keywords

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

Cite this