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.
Citation
Journal of Optimization Theory and Applications, 136 (2), pp. 211 - 228 (2008).