A faster dual algorithm for the Euclidean minimum covering ball problem

Marta Cavaleiro; Farid Alizadeh

doi:10.1007/s10479-018-3123-5

A faster dual algorithm for the Euclidean minimum covering ball problem

Marta Cavaleiro, Farid Alizadeh

Rutgers Business School, Management & Information Systems

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 Rⁿ. Each iteration of their algorithm has a computational complexity of at least O(n³). 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(n²) iteration.

Original language	English (US)
Journal	Annals of Operations Research
DOIs	https://doi.org/10.1007/s10479-018-3123-5
State	Accepted/In press - 2020

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

Access to Document

10.1007/s10479-018-3123-5

Cite this

@article{9206c530fb534eb39ae44eb406e6e9fa,

title = "A faster dual algorithm for the Euclidean minimum covering ball problem",

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.",

keywords = "1-Center, Computational geometry, Minimum covering ball, Minmax location, Smallest enclosing ball",

author = "Marta Cavaleiro and Farid Alizadeh",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2020",

doi = "10.1007/s10479-018-3123-5",

language = "English (US)",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - A faster dual algorithm for the Euclidean minimum covering ball problem

AU - Cavaleiro, Marta

AU - Alizadeh, Farid

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - 1-Center

KW - Computational geometry

KW - Minimum covering ball

KW - Minmax location

KW - Smallest enclosing ball

UR - http://www.scopus.com/inward/record.url?scp=85081245287&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081245287&partnerID=8YFLogxK

U2 - 10.1007/s10479-018-3123-5

DO - 10.1007/s10479-018-3123-5

M3 - Article

AN - SCOPUS:85081245287

SN - 0254-5330

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -

A faster dual algorithm for the Euclidean minimum covering ball problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this