Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10589-005-4565-7
Title: Efficient algorithms for the smallest enclosing ball problem
Authors: Zhou, G.
Tohemail, K.-C. 
Sun, J. 
Keywords: Computational geometry
Second order cone programming
Smoothing approximation
Issue Date: Feb-2005
Citation: Zhou, G., Tohemail, K.-C., Sun, J. (2005-02). Efficient algorithms for the smallest enclosing ball problem. Computational Optimization and Applications 30 (2) : 147-160. ScholarBank@NUS Repository. https://doi.org/10.1007/s10589-005-4565-7
Abstract: Consider the problem of computing the smallest enclosing ball of a set of m balls in ℛ n. Existing algorithms are known to be inefficient when n > 30. In this paper we develop two algorithms that are particularly suitable for problems where n is large. The first algorithm is based on log-exponential aggregation of the maximum function and reduces the problem into an unconstrained convex program. The second algorithm is based on a second-order cone programming formulation, with special structures taken into consideration. Our computational experiments show that both methods are efficient for large problems, with the product mn on the order of 10 7. Using the first algorithm, we are able to solve problems with n = 100 and m = 512,000 in about 1 hour.
Source Title: Computational Optimization and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/114324
ISSN: 09266003
DOI: 10.1007/s10589-005-4565-7
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

19
checked on May 19, 2018

WEB OF SCIENCETM
Citations

15
checked on Apr 3, 2018

Page view(s)

41
checked on May 18, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.