A dual simplex-type algorithm for the smallest enclosing ball of balls

Marta Cavaleiro () and Farid Alizadeh ()
Additional contact information
Marta Cavaleiro: Rutgers University
Farid Alizadeh: Rutgers University

Computational Optimization and Applications, 2021, vol. 79, issue 3, No 8, 767-787

Abstract: Abstract We develop a dual simplex-type algorithm for computing the smallest enclosing ball of a set of balls and other closely related problems. Our algorithm employs a pivoting scheme resembling the simplex method for linear programming, in which a sequence of exact curve searches is performed until a new dual feasible solution with a strictly smaller objective function value is found. We utilize the Cholesky factorization and procedures for updating it, yielding a numerically stable implementation of the algorithm. We show that our algorithm can efficiently solve instances of dimension 5000 with 100000 points, often within minutes.

Keywords: Smallest enclosing ball of balls; Smallest intersecting ball of balls; Simplex-type methods; Second-order cone programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00283-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:79:y:2021:i:3:d:10.1007_s10589-021-00283-6

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00283-6

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().