2008 International Conference on Computational Sciences and Its Applications
Full text: Download
We study the problem of computing the minimum volume enclosing ellipsoid (MVEE) containing a given set of ellipsoids S = {E1, E2, hellip, En} sube Ropfd. We show how to efficiently compute a small set X sube S of size at most a = |X| = O(d2/epsi ) whose minimum volume ellipsoid is an (1 + epsi)-approximation to the minimum volume ellipsoid of S. We use an augmented real num ber model of computation to achieve a running time of O(alpha(ndomega + d3)) where omega < 2.376 is the exponent of square matrix multiplication. This is the best known complexity for solving the MVEE problem when n Gt d and e is large. The algorithm is built on the previous work by Kumar and Yrfdirim [17].