Computing Minimum Volume Enclosing Axis-Aligned Ellipsoids

Piyush Kumar (piyushacm.org)
E. Alper Yildirim (yildirimbilkent.edu.tr)

Abstract: Given a set of points $\cS = \{x^1,\ldots,x^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze an algorithm for the problem of computing a $(1 + \eps)$-approximation to the the minimum volume axis-aligned ellipsoid enclosing $\cS$. We establish that our algorithm is polynomial for fixed $\eps$. In addition, the algorithm returns a small core set $\cX \subseteq \cS$, whose size is independent of the number of points $m$, with the property that the minimum volume axis-aligned ellipsoid enclosing $\cX$ is a good approximation of the minimum volume axis-aligned ellipsoid enclosing $\cS$. Our computational results indicate that the algorithm exhibits significantly better performance than that indicated by the theoretical worst-case complexity result.

Keywords: Axis-aligned ellipsoids, enclosing ellipsoids, core sets, approximation algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization

Citation: Journal of Optimization Theory and Applications, 136 (2), pp. 211 - 228 (2008).

Download:

Entry Submitted: 06/28/2006
Entry Accepted: 06/28/2006
Entry Last Modified: 02/06/2008

Modify/Update this entry