Optimization Online


Two Algorithms for the Minimum Enclosing Ball Problem

E. Alper YILDIRIM (yildirim***at***bilkent.edu.tr)

Abstract: Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze two algorithms for the problem of computing a $(1 + \eps)$-approximation to the radius of the minimum enclosing ball of $\cA$. The first algorithm is closely related to the Frank-Wolfe algorithm with a proper initialization applied to the dual formulation of the minimum enclosing ball problem. We establish that this algorithm converges in $O(1/\eps)$ iterations with an overall complexity bound of $O(mn/\eps)$ arithmetic operations. In addition, the algorithm returns a ``core set'' of size $O(1/\eps)$, which is independent of both $m$ and $n$. The latter algorithm is obtained by incorporating ``away'' steps into the former one at each iteration and achieves the same asymptotic complexity bound as the first one. While the asymptotic bound on the size of the core set returned by the second algorithm also remains the same as the first one, the latter algorithm has the potential to compute even smaller core sets in practice since, in contrast with the former one, it allows ``dropping'' points from the working core set at each iteration. Our computational results indicate that the latter algorithm indeed returns smaller core sets in comparison with the first one. We also discuss how our algorithms can be extended to compute an approximation to the minimum enclosing ball of other input sets. In particular, we establish the existence of a core set of size $O(1/\eps)$ for a much wider class of input sets.

Keywords: Minimum enclosing balls, core sets, approximation algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: SIAM Journal on Optimization, 19 (3) pp. 1368-1391 (2008)


Entry Submitted: 05/04/2007
Entry Accepted: 05/04/2007
Entry Last Modified: 09/15/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society